「2018 ACM-ICPC Shenyang - Online」F - Fantastic Graph (网络流)

发表于 | 分类于 ， ，

F-Fantastic Graph
网络流建模，无源汇有上下界可行流问题

题意

给定一个二分图和一系列匹配边，求解是否存在匹配边的选择组合，使二分图中的每个点度数$d$满足$l≤d≤r$。

思路

对于原二分图建立网络流模型。添加源汇点$s,t$,将其视为有上下界可行流问题求解。

解法

对于二分图中的每一条边，在网络流中边的流量为上界-下界。为了保证流量平衡，对于每一个出度为$d_i$的 左侧结点$X_i$,从源点建立一条容量为$d_i$的边；同样的，对于每一个出度为$d_i$的右侧结点$Y_i$,建立一条从$Y_i$到汇点的容量为$d_i$的边。建模完成后，从$s$到$t$跑一次最大流即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn=2000+10;
const int INF=0x3f3f3f3f;
int n,m,k,high,low;

const int MAX_V=6000+10;
int g[maxn][maxn];

//用于表示边的结构体（终点，流量，反向边）
struct edge{int to,cap,rev;};

vector<edge> G[MAX_V];	//图的邻接表表示
int level[MAX_V];	//顶点到源点的距离标号
int iter[MAX_V];	//当前弧

void add(int from,int to,int cap)
{
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

//计算从源点出发的距离标号
void bfs(int s)
{
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty())
	{
		int v=que.front();que.pop();
		for(int i=0;i<G[v].size();i++)
		{
			edge &e=G[v][i];
			if(e.cap>0&&level[e.to]<0)
			{
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

//通过DFS寻找增广路
int dfs(int v,int t,int f)
{
	if(v==t) return f;
	for(int &i=iter[v];i<G[v].size();i++)
	{
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to])
		{
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0)
			{
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t)
{
	int flow=0;
	for(;;)
	{
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f=dfs(s,t,INF))>0) flow+=f;
	}
}


int main()
{
    int u,v,deu[maxn],dev[maxn],cnt=0;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        for(int i=0;i<MAX_V;i++) G[i].clear();
        memset(g,0,sizeof g);
        memset(deu,0,sizeof deu);
        memset(dev,0,sizeof dev);
        scanf("%d%d",&low,&high);
        memset(G,0,sizeof G);
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&u,&v);
            g[u][v]++;
            deu[u]++;
            dev[v]++;
        }
        bool flag=true;
        for(int i=1;i<=n;i++) if(deu[i]<low) flag=false;
        for(int i=1;i<=m;i++) if(dev[i]<low) flag=false;
        //如果某点最大可达到的流量小于low，输出no
        if(!flag)
        {
            printf("Case %d: %s\n",++cnt,flag?"Yes":"No");
            continue;
        }
        int s=n+m+1,e=s+1,sum=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(!g[i][j]) continue;
                add(i,j,high-low);
            }
        }
        for(int i=1;i<=n;i++) add(s,i,deu[i]),sum+=deu[i];
        for(int i=1;i<=m;i++) add(i,e,dev[i]);
        int ans=max_flow(s,e);
        if(ans!=sum) flag=false;
        printf("Case %d: %s\n",++cnt,flag?"Yes":"No");
    }
    return 0;
}