Fantastic Graph（有源汇有上下界可行流）

Fantastic Graph（有源汇有上下界可行流）

"Oh, There is a bipartite graph.""Make it Fantastic."

X wants to check whether a bipartite graph is a fantastic graph. He has two fantastic numbers, and he wants to let all the degrees to between the two boundaries. You can pick up several edges from the current graph and try to make the degrees of every point to between the two boundaries. If you pick one edge, the degrees of two end points will both increase by one. Can you help X to check whether it is possible to fix the graph?

Input

There are at most 3030 test cases.

For each test case,The first line contains three integers NN the number of left part graph vertices, MM the number of right part graph vertices, and KK the number of edges ( 1 \le N \le 20001≤N≤2000,0 \le M \le 20000≤M≤2000,0 \le K \le 60000≤K≤6000 ). Vertices are numbered from 11 to NN.

The second line contains two numbers L, RL,R (0 \le L \le R \le 300)(0≤L≤R≤300). The two fantastic numbers.

Then KK lines follows, each line containing two numbers UU, VV (1 \le U \le N,1 \le V \le M)(1≤U≤N,1≤V≤M). It shows that there is a directed edge from UU-th spot to VV-th spot.

Note. There may be multiple edges between two vertices.

Output

One line containing a sentence. Begin with the case number. If it is possible to pick some edges to make the graph fantastic, output ​​"Yes"​​​ (without quote), else output ​​"No"​​ (without quote).

样例输入

3 3 7 2 3 1 2 2 3 1 3 3 2 3 3 2 1 2 1 3 3 7 3 4 1 2 2 3 1 3 3 2 3 3 2 1 2 1

样例输出

Case 1: Yes Case 2: No

无源汇有上下界可行流的建图方法

需要新建源点汇点。

需要转化为最大流问题，所以把下界变为0.

用to数组表示每个点    进来的下届流量    减去    出去的下界流量。

这时候多了或者少了的流量需要处理。

如果i点的to数组为正，需要多找点来源，则需要由源点向该点连边，容量为to[i].

如果i点的to数组为负，需要多流出去点，则需要由该点向汇点连边，容量为-to[i].

图中的每条边的容量设置为R-L即可。

如果是有源汇的，需要保持流量平衡。

连接原图的源点s，和汇点t。让多余的流量循环。变成无源汇的上下界可行流。

跑完最大流，看看源点的边是否满流

代码：

#include #include #include #include using namespace std ;#define copy( a , x ) memcpy ( a , x , sizeof a )typedef long long LL ;const int MAXN = 15000 ;const int MAXE = 100000 ;const int MAXQ = 100000 ;const int INF = 0x3f3f3f3f ;struct Edge { int v , n ; LL c ; Edge ( int var = 0 , LL cap = 0 , int next = 0 ) : v ( var ) , c ( cap ) , n ( next ) {}} ;struct netWork { Edge edge[MAXE] ; int adj[MAXN] , cntE ; int cur[MAXN] , d[MAXN] , num[MAXN] , pre[MAXN] ; bool vis[MAXN] ; int Q[MAXQ] , head , tail ; int s , t , nv ; LL flow ; void init () { cntE = 0 ; memset(adj,-1,sizeof(adj)); } void addedge ( int u , int v , LL c , LL rc = 0 ) { edge[cntE] = Edge ( v , c , adj[u] ) ; adj[u] = cntE ++ ; edge[cntE] = Edge ( u , rc , adj[v] ) ; adj[v] = cntE ++ ; } void rev_Bfs () { memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); d[t] = 0 ; vis[t] = 1 ; head = tail = 0 ; Q[tail ++] = t ; num[0] = 1 ; while ( head != tail ) { int u = Q[head ++] ; for ( int i = adj[u] ; ~i ; i = edge[i].n ) { int v = edge[i].v ; if ( vis[v] ) continue ; vis[v] = 1 ; d[v] = d[u] + 1 ; ++ num[d[v]] ; Q[tail ++] = v ; } } } LL ISAP () { copy ( cur , adj ) ; rev_Bfs () ; flow = 0 ; int i , u = pre[s] = s ; while ( d[s] < nv ) { if ( u == t ) { LL f = INF ; int pos ; for ( i = s ; i != t ; i = edge[cur[i]].v ) if ( f > edge[cur[i]].c ) f = edge[cur[i]].c , pos = i ; for ( i = s ; i != t ; i = edge[cur[i]].v ) edge[cur[i]].c -= f , edge[cur[i] ^ 1].c += f ; u = pos ; flow += f ; } for ( i = cur[u] ; ~i ; i = edge[i].n ) if ( edge[i].c && d[u] == d[edge[i].v] + 1 ) break ; if ( ~i ) { cur[u] = i ; pre[edge[i].v] = u ; u = edge[i].v ; } else { if ( 0 == ( -- num[d[u]] ) ) break ; int mmin = nv ; for ( i = adj[u] ; ~i ; i = edge[i].n ) if ( edge[i].c && mmin > d[edge[i].v] ) cur[u] = i , mmin = d[edge[i].v] ; d[u] = mmin + 1 ; ++ num[d[u]] ; u = pre[u] ; } } return flow ; }} ;netWork net ;int pp;int n,m,k;LL to[MAXN];void work () { net.init () ; memset(to,0,sizeof(to)); int ss=n+m+1,tt=ss+1; net.s = tt+1 , net.t = net.s+1, net.nv = net.t + 1 ; net.addedge(tt,ss,INF); int L,R; scanf("%d%d",&L,&R); int u,v; for(int i=1;i<=k;i++) { scanf("%d%d",&u,&v); net.addedge(u,n+v,1); } for(int i=1;i<=n;i++) { net.addedge(ss,i,R-L); to[ss]-=L; to[i]+=L; } for(int i=1;i<=m;i++) { net.addedge(i+n,tt,R-L); to[i+n]-=L; to[tt]+=L; } LL sum=0; for(int i=1;i<=n+m+2;i++) { if(to[i]>0) { net.addedge(net.s,i,to[i]); sum+=to[i]; } else { net.addedge(i,net.t,-to[i]); } } LL flow =net.ISAP(); printf("Case %d: ",pp++); if(flow==sum)printf ("Yes\n"); else printf ("No\n");}int main(){ pp=1; while(~scanf("%d%d%d",&n,&m,&k)) { work(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。