ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph

 F. 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

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

赛场上现学的上下界可行流。一开始我还写错了。但是数据出奇的水，居然让我给过了。

网上还有一种贪心的做法，我一开始也想到过，但是觉得有漏洞所以就没有尝试，但是可能是因为数据太水了吧，还是说其实是对的我想错了，就也不知道了。

先讲一下上下界可行流。

对于一副循环图（即无源点和汇点，起始点和终末点之间存在一条容量无限大的边）来说，假设其中的每条边的流量都介于[l,r]直接，我们不妨将l取出，将原边变为[0,r-l]，与一条容量为l的必行边，并在这条边中间插入两个点，设为x，y，细节见图示

我们不难发现从x到y的流量只有x->y一条，因此其x->y的最大流也就是3，于是我们可以据此推理出假使存在一条从y到x的最大流等于3时就是所有的必行边都被走过了，那么这个图就是可行的。

但是本题是一个有汇源点的图，所以我们要想办法将之转化为循环图，具体方法就是在汇点和源点直接也连上一条无穷大的边即可。需要注意的是：

从汇点向源点连！

从汇点向原点连！

从汇点向原点连！

重要的事情说三遍。

AC代码：

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=25005;//点数
const int inf=0x3f3f3f3f;
struct Edge{
	int from,to,cap,flow;//起点，终点，容量，流量
	Edge(){}
	Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
struct Dinic{
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[maxn];//邻接表
	bool vis[maxn];//BFS使用
	int d[maxn];//从起点到i的距离
	int cur[maxn];//当前弧下标

	void init(int n)//n为点的数量
	 {
	 	this->n=n;
	 	for(int i=0;i<=n;i++) G[i].clear();
	 	edges.clear();
	 }


	void AddEdge(int from,int to,int cap)//增加边
	{
		edges.push_back(Edge(from,to,cap,0));
		edges.push_back(Edge(to,from,0,0));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}


	bool bfs()//用bfs来构筑层次图
	{
		memset(vis,0,sizeof(vis));
		queue<int> Q;
		Q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!Q.empty())
		{
			int x=Q.front();Q.pop();
			for(int i=0;i<G[x].size();i++)
			{
				Edge& e=edges[G[x][i]];
				if(!vis[e.to]&&e.cap>e.flow)//只考虑参与网络的弧
				{
					vis[e.to]=1;
					d[e.to]=d[x]+1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}


	int dfs(int x,int a)//用dfs构筑增广路
	{
		if(x==t||a==0) return a;
		int flow=0,f;
		for(int& i=cur[x]; i<G[x].size() ;i++)
		{
			Edge& e=edges[G[x][i]];
			if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(!a) break;
			}
		}
		return flow;
	}


	int Maxflow(int s,int t)//求最大流
	{
		this->s=s,this->t=t;
		int flow=0;
		while(bfs())
		{
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,inf);
		}
		return flow;
	}
};
int main()
{
	int n,m;
	int k;
	int kace=1;
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		int l,r;
		scanf("%d%d",&l,&r);
		Dinic p;
		p.init(25000);
		int s=0,t=25000;
		p.AddEdge(t,s,inf);
		int x=24999,y=24998;
		for(int i=1;i<=n;i++)
		{
			p.AddEdge(s,i,r-l);
			p.AddEdge(s,x,l);
			p.AddEdge(y,i,l);
		}
		for(int i=1;i<=m;i++)
		{
			int point=i+20005;
			p.AddEdge(point,t,r-l);
			p.AddEdge(point,x,l);
			p.AddEdge(y,t,l);
		}
		while(k--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			v+=20005;
			p.AddEdge(u,v,1);
		}
		p.Maxflow(y,x);
		int flag=1;
		for(int i=0;i<p.G[y].size();i++)
		{
			Edge e=p.edges[p.G[y][i]];
			//cout<<e.cap<<' '<<e.flow<<endl;
			if(e.cap!=e.flow)
			{
				flag=0;
				break;
			}
		}
		printf("Case %d: ",kace++);
		if(flag)
		{
			cout<<"Yes"<<endl;
		}
		else
		{
			cout<<"No"<<endl;
		}
	}
}