首页 > 代码库 > SPOJ IM_Intergalactic Map

SPOJ IM_Intergalactic Map

2024-07-13 05:23:48   216人阅读

判断能否从一个点同时找出两条不相交的路径到另外两个点。

保证路径不相交，那么需要拆点。然后？好像就没什么了，直接最大流即可。

不过，，，不需要求出所有的最大流，只要跑两次EK看看能否增广两次就行了。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <map>#define maxn 2001000#define maxm 5002000using namespace std;int L[maxn],R[maxn],Li[maxn],Ri[maxn];int to[maxm],next[maxm],c[maxm],first[maxn],edge,node;int from[maxn],tag[maxn],TAG=520;int Q[maxm],bot,top;int n,m,s,t,T;int addnode(){    first[++node]=-1;    return node;}void addedge(int U,int V){    edge++;    to[edge]=V,c[edge]=1,next[edge]=first[U],first[U]=edge;    edge++;    to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}void _input(){    int U,V;    node=0,edge=-1;    scanf("%d%d",&n,&m);    while (m--)    {        scanf("%d%d",&U,&V);        if (Li[U]!=TAG) Li[U]=TAG,L[U]=addnode(),R[U]=addnode(),addedge(L[U],R[U]);        if (Li[V]!=TAG) Li[V]=TAG,L[V]=addnode(),R[V]=addnode(),addedge(L[V],R[V]);        addedge(R[U],L[V]),addedge(R[V],L[U]);    }    t=addnode();    if (Li[2]==TAG) s=R[2];        else s=addnode();    if (Li[1]==TAG) addedge(R[1],t);    if (Li[3]==TAG) addedge(R[3],t);}bool EK(){    Q[bot=top=1]=s,tag[s]=++TAG,from[s]=-1;    while (bot<=top)    {        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])            if (c[i]>0 && tag[to[i]]!=TAG)            {                Q[++top]=to[i],from[to[i]]=i,tag[to[i]]=TAG;                if (to[i]==t)                {                    for (int k=t; from[k]!=-1; k=to[from[k]^1])                        c[from[k]]--,c[from[k]^1]++;                    return true;                }            }    }    return false;}int main(){    scanf("%d",&T);    while (T--)    {        _input();        if (EK() && EK()) puts("YES");            else puts("NO");    }    return 0;}


联系
我们