Tang-Dreamoon's Blog

bzoj dance跳舞

发表于 | 分类于 ， ，

入门网络流——注意流量的定义

　　题意自己戳进去看吧，很好理解：bzoj 1305

　　题解：这道题目很显然是要最优转判定的，比如判定能不能有Ｔ轮，现在考虑怎么转换呢，对于每个男生建立三个定点——表示全体、得到喜欢的、得到不喜欢的，那么源点向全体连一条容量为T的边，全体向喜欢的连无穷大的边，全体向不喜欢的连容量为K的边，然后女生也分成这样的三个跟汇点连边，然后喜欢和喜欢连，不喜欢和不喜欢连容量都为一的边就好了。

　　我思故我在：这个题一开始的思路其实很容易想到要从男生向女生连容量为一的边，表示跳一支舞。但是我们发现如果直接去连边是无法区分喜欢和不喜欢，而且无法控制流向不喜欢的<=K，所以我们很自然的想到要将每个人至少拆成“喜欢和不喜欢”两个点。但是我一开始愚蠢的认为应该向全体点连一条容量为正无穷的边，但是后来我发现这是因为我没有搞清楚这个题流量的定义：流量即为所跳的总舞曲数。既然这样我们就应该规定每个人跳的舞曲数目一样，即应该限制每个男生的入流量一样、每个女生的出流量完全一样。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,k;
int tot=0;
struct table{
	int to,id;
};
vector<table> ve[100000];
int f[400000];
int deep[100000];
int min(int a,int b)
{
	if(a<=b) return a;
	else return b;
}
bool bfs()
{
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	deep[0]=0;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(deep[y.to]==-1&&f[y.id]>0)
			{
				deep[y.to]=deep[x]+1;
				q.push(y.to);
			}
		} 
	}
	return deep[6*n+1]!=-1;
}
int zeng(int a,int b)
{
	if(a==6*n+1) return b;
	int r=0,t;
	for(int i=0;i<ve[a].size()&&b>r;i++)
	{
		table y=ve[a][i];
		if(deep[y.to]==deep[a]+1&&f[y.id]>0)
		{
			t=zeng(y.to,min(b-r,f[y.id]));
			r+=t,f[y.id]-=t,f[y.id^1]+=t;
		}
	}
	if(!r) deep[a]=-1;
	return r;
}
int dinic()
{
	int ans=0,now;
	while(bfs())
	{
		while(now=zeng(0,247483647)) ans+=now;
	}
	return ans;
}
char map[100][100];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",map[i]+1);
	}
	for(int t=0;t<=n+1;t++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(map[i][j]=='Y')
				{
					ve[i].push_back((table){j+n,tot}),f[tot++]=1;
					ve[j+n].push_back((table){i,tot}),f[tot++]=0;
				}
				else
				{
					ve[i+2*n].push_back((table){j+2*n+n,tot}),f[tot++]=1;
					ve[j+2*n+n].push_back((table){i+2*n,tot}),f[tot++]=0;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			ve[i+4*n].push_back((table){i,tot}),f[tot++]=247483647;
			ve[i].push_back((table){i+4*n,tot}),f[tot++]=0;
			ve[i+4*n].push_back((table){i+2*n,tot}),f[tot++]=k;
			ve[i+2*n].push_back((table){i+4*n,tot}),f[tot++]=0;
			ve[0].push_back((table){i+4*n,tot}),f[tot++]=t;
			ve[i+4*n].push_back((table){0,tot}),f[tot++]=0;
		}
		for(int i=1;i<=n;i++)
		{
			ve[i+n].push_back((table){i+5*n,tot}),f[tot++]=247483647;
			ve[i+5*n].push_back((table){i+n,tot}),f[tot++]=0;
			ve[i+3*n].push_back((table){i+5*n,tot}),f[tot++]=k;
			ve[i+5*n].push_back((table){i+3*n,tot}),f[tot++]=0;
			ve[i+5*n].push_back((table){6*n+1,tot}),f[tot++]=t;
			ve[6*n+1].push_back((table){i+5*n,tot}),f[tot++]=0;
		}
		if(dinic()!=n*t)
		{
			cout<<t-1<<endl;
			break;
		}
		else
		{
			for(int i=0;i<=6*n+1;i++)
			{
				ve[i].clear();
			}
			tot=0;
		}
	}
	return 0;
}