题目大意:给张无向图,有两个人a,b分别从各自的起点走向各自的终点,走A,B个来回,图里有些边只能走两次,求问是否能满足a,b的需求
按照题目给的表建图
S连a1,b1
a2,b2连T
跑最大流看是否满流
为了防止a1跑到b2的情况
第二遍
S连a1,b2
a2,b1连T
若还是满流说明没问题
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define INF 0x7fffffff using namespace std; , maxn = ; int n,a1,a2,A,b1,b2,B; ]; struct node{ int to[maxe],next[maxe],flow[maxe]; int head[maxn],h[maxn],tot,s,t; ; t=n+; memset(head,-,;} void insert(int u, int v, int f){ to[++tot]=v; next[tot]=head[u]; flow[tot]=f; head[u]=tot; to[++tot]=u; next[tot]=head[v]; flow[tot]=; head[v]=tot; } bool bfs(){ memset(h,-,sizeof(h)); queue<int> Q; Q.push(s); h[s]=; while (!Q.empty()){ int now=Q.front(); Q.pop(); ; i=next[i]){ int v=to[i]; ){ h[v]=h[now]+; Q.push(v); } } } ) ; ; } int dfs(int x, int mx){ if (x==t) return mx; ; ; i=next[i]){ int v=to[i]; ){ int f=dfs(v,min(flow[i],mx)); flow[i]-=f; flow[i^]+=f; res+=f; mx-=f; if (!mx) break; } } ; return res; } int maxflow(){ ; while (bfs()) ans+=dfs(s,INF); return ans; } }x,y; int main(){ while (scanf("%d%d%d%d%d%d%d", &n, &a1, &a2, &A, &b1, &b2, &B)!=EOF){ a1++; a2++; b1++; b2++; A*=; B*=; x.init(); ; i<=n; i++){ scanf(); ; j<=n; j++){ ); else if (st[j]=='N') x.insert(i,j,INF); } } y=x; , t=n+; x.insert(s,a1,A); x.insert(a2,t,A); x.insert(s,b1,B); x.insert(b2,t,B); y.insert(s,a1,A); y.insert(a2,t,A); y.insert(s,b2,B); y.insert(b1,t,B); if (x.maxflow()==A+B && y.maxflow()==A+B) printf("Yes\n"); else printf("No\n"); } ; }