首页 > 代码库 > SPOJ IM_Intergalactic Map
SPOJ IM_Intergalactic Map
判断能否从一个点同时找出两条不相交的路径到另外两个点。
保证路径不相交,那么需要拆点。然后?好像就没什么了,直接最大流即可。
不过,,,不需要求出所有的最大流,只要跑两次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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。