[图论][SDOI2009]Elaxia的路线

发布于 2018-09-16  505 次阅读


题目大意

给你一张n个点的无向图,求两对点间最短路的最长公共路径。
无重边,无自环
n<=1500

读完题发现让你在一张无向图中找两对点间最短路的最长公共路径。
考虑什么样的路径才会对答案有贡献。
设这两对点对为(x1,y1),(x2,y2);
显然只有那些在(x1->y1)又在(x2->y2)的最短路上的边才行
所以我们可以对这4个点跑一个最短路,记下这4个点到每个点的最短路为dis[1],dis[2],dis[3],dis[4]
如果一条边满足条件,

$min(dis[1][u],dis[1][v])+min(dis[2][u],dis[2][v])+val=dis[1][y1];$
$min(dis[3][u],dis[3][v])+min(dis[4][u],dis[4][v])+val=dis[3][y2];$

然后把这些边连起来,大概是会构成许多张图,我们用拓扑排序求最长路就行,显然满足条件的公共路径是一条链

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

#define int long long
using namespace std;
const int N=1505;
const int INF=0x3f3f3f3f;

int n,m,ans;
int x1,x2,y1,y2;
struct data
{
    int v,nxt,val,u;
}edge[N*N];
int cnt,alist[N];
inline void add(int u,int v,int val){edge[++cnt]=(data){v,alist[u],val,u},alist[u]=cnt;}

struct data1
{
    int v,nxt,val;
}edge1[N*N];
int cnt1,alist1[N],du[N];
inline void add1(int u,int v,int val){edge1[++cnt1]=(data1){v,alist1[u],val},alist1[u]=cnt1,du[v]++;}

struct nod
{
    int num,val;
    friend bool operator <(nod a,nod b){return a.val>b.val;}
};
bool vis[N];int dis[5][N],tot;
int len1,len2;
inline void dj(int st)
{
    priority_queue<nod> q;tot++;dis[tot][st]=0;memset(vis,false,sizeof vis);
    nod pack;pack=(nod){st,0};q.push(pack);
    while(!q.empty())
    {
        int now=q.top().num;q.pop();
        if(vis[now]) continue;
        vis[now]=true;
        for(int i=alist[now];i;i=edge[i].nxt)
        {
            int v=edge[i].v;int val=edge[i].val;
            if(dis[tot][v]>dis[tot][now]+val)
            {
                dis[tot][v]=dis[tot][now]+val;
                nod pack=(nod){v,dis[tot][v]};
                q.push(pack);
            }
        }
    } 
}
inline bool fuck(int x)
{
    if(dis[1][x]+dis[2][x]==len1&&dis[3][x]+dis[4][x]==len2) return 1;
    return false;
}
int d[N];
inline void fuck()
{
    queue<int> q1;
    for(int i=1;i<=n;++i) if(!du[i]) q1.push(i);
    while(!q1.empty())
    {
        int now=q1.front();q1.pop();
        for(int i=alist1[now];i;i=edge1[i].nxt)
        {
            int v=edge1[i].v;
            d[v]=max(d[v],d[now]+edge1[i].val);
            ans=max(ans,d[v]);
            du[v]--;
            if(!du[v]) q1.push(v);
        }
    }
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
    for(int i=1,x,y,z;i<=m;++i)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    memset(dis,INF,sizeof dis);
    dj(x1);dj(y1);
    dj(x2);dj(y2);
    for(int i=1;i<=cnt;i+=2)
    {
        int x=edge[i].v,y=edge[i].u,val=edge[i].val;
        len1=min(dis[1][x],dis[1][y])+min(dis[2][x],dis[2][y])+val;
        len2=min(dis[3][x],dis[3][y])+min(dis[4][x],dis[4][y])+val;
        if(len1==dis[1][y1]&&len2==dis[3][y2])
        {
            if(dis[1][x]<dis[1][y]) add1(x,y,val);
            else add1(y,x,val);
        }
    }
    fuck();
    printf("%d",ans);
} 
0.00 avg. rating (0% score) - 0 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。