建图:
首先加一个源点s和汇点t,分别连接在二分图的左边和右边,每条弧的上下界为【L, R】,二分图左边和右边之间连弧上下界为【0,1】,其实就相当于连弧为1。
然后问题就转换为:有源汇最大流。
继续建图:
建立弧<t,s><,容量下界为00,上界为∞∞。
加一个超级源ss和超级汇tt
对于所有有上下界的弧(也就是s,t分别连接左边和右边的弧)进行分边
一条为<ss,v>,容量为L;
一条为<u,tt>>,容量为L;
一条为<u,v>,容量为R-L。
其中前两条弧一般称为附加弧。
然后跑一遍最大流,如果ss所有的出边(或者是TT所有的入边)都满流,就输出Yes
以后再加图说明吧....
(代码说明一下.. 0为超级源,NV为超级汇, NV-2为源, NV-1为汇)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = ;
const int inf = 0x3f3f3f; struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}
}; struct Din
{
int s,t;
vector<Edge>edges;
vector<int>G[N];
bool vis[N];
int d[N];
int cur[N]; void addedge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,));
edges.push_back(Edge(to,from,,));
int m=edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool bfs()
{
memset(vis,,sizeof(vis));
queue<int>Q;
Q.push(s);
d[s]=;
vis[s]=;
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=; i<G[x].size(); i++)
{
Edge&e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=;
d[e.to]=d[x]+;
Q.push(e.to);
}
}
}
return vis[t];
} int dfs(int x,int a)
{
if(x==t||a==)
return a;
int flow=,f;
for(int i=cur[x]; i<G[x].size(); i++)
{
Edge&e=edges[G[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>)
{
e.flow += f;
edges[G[x][i]^].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=;
while(bfs())
{
memset(cur,,sizeof(cur));
flow += dfs(s,inf);
}
return flow;
}
}; int main()
{
int N,F,D;
int cnt = ;
while(scanf("%d%d%d",&N,&F,&D) != EOF)
{
Din tmp;
int flag = ;
int NV = N+F++, NE=;
int a, b;
int l, r;
scanf("%d%d",&l, &r);
for(int i=; i<D; i++)
{
scanf("%d%d",&a, &b);
tmp.addedge(a,N+b, );
}
for(int i=; i<=N; i++)
{
tmp.addedge(NV-,i, r-l);
tmp.addedge(,i, l);
tmp.addedge(NV-,NV, l);
}
for(int i=; i<=F; i++)
{
tmp.addedge(N+i,NV-, r-l);
tmp.addedge(,NV-, l);
tmp.addedge(N+i,NV, l);
}
tmp.addedge(NV-,NV-, inf);
int tt = tmp.Maxflow(NE,NV);
for(int i=; i<tmp.G[].size(); i++)
{
Edge &e=tmp.edges[tmp.G[][i]];
if(e.flow < l){
flag = ;
break;
}
}
cnt++;
if(flag)
printf("Case %d: Yes\n", cnt);
else
printf("Case %d: No\n", cnt);
}
}