自从上次懒羊羊红酒促销会后，越来越多的羊族及朋友喜欢上了yesky wine。懒羊羊跟叶老师申请要销售更多的yesky wine红酒。为此，他还准备改造他的红酒供应系统。红酒供应系统由一个酒厂，一个红酒储藏站，若干供应站和管道组成。当然，酒厂就位于叶老师所在的浙江理工大学后花园。中转站位于懒羊羊开设的很多酒吧、餐厅和其他红酒供应场所，需要时可以销售。红酒储藏站的位置非常神秘，不过这个对整个系统不是很重要。
红酒供应管道连接了刚才提到的各站点。酒厂至少连接了1个站点，神秘的储藏站也至少连接了一个站点。当然，极端的情况下，可能酒厂直接连接到神秘的储藏站，而没有其他任何中转站。
从酒厂出来的红酒通过管道充满了（经常是）一些站点并且能自动流到下一站点。
红酒在系统里流动，从某个站点流出的红酒不会返回到该站点，也就是说系统中不会出现回路。管道中酒的流向也是固定的不会回流。酒厂的酒是足够的，管道中的经常是有红酒流的。
现在的红酒供应系统有一些管道是多余的。你需要对这些管道进行优化，去掉一些多余的管道使得每个中转站都能得到红酒供应，同时也能流转到神秘的储藏站。当然，管道的容量是足够大的。
给你这个供酒系统的布置图，你能帮懒羊羊看看最多可以去掉多少根管道吗？
第一行输入2个整数N,M(1<=N<=2000,0<=M<=5000),N是系统中红酒站点，包括酒厂和储藏站。M是管道数量。站点用1,2，...N标记。
接下来是M行，每行2个整数X和Y,标记着管道是从X流向Y（1<=x,y<=N）,数据保证每个管道连接的2个站点是独一无二的，也不会流向自己。只有一个站点是没有流进去的，那就是酒厂，也只有一个站点是没有流出的，那就是神秘的储藏站。
2020年浙江理工大学校赛
思路
感觉这才是本场签到题，可惜被C搞了心态没看题
这道题给人的感觉就是要往二分图上想
给出一个有源有汇的有向无环图，问如何用最少的边把整张图跑满
因为题目保证了能流满（∵系统中有多余的管道）
在此前提下，仅需要保证图在最少的连边情况下跑通即可
何为最少：删去一条边则有站点未被经过，可以看做是未达到最大流
那么可得到 要求1：最少时，每个中转站至少有一个入点和一个出点
我们通过观察可以发现，此时求最大流的过程就相当于每两个中转站之间去架设管道匹配
为了方便操作，我们使用匈牙利算法来计算必须参与匹配的管道数
对于没有达到要求1的中转站，我们把他本来连接的但此时暂未选入的管道加入网络中，来保证我们的图可以跑通
CODE
1 #include <bits/stdc++.h>
2 #define dbg(x) cout << #x << "=" << x << endl
3 #define eps 1e-8
4 #define pi acos(-1.0)
5
6 using namespace std;
7 typedef long long LL;
8
9 template<class T>inline void read(T &res)
10 {
11 char c;T flag=1;
12 while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)flag=-1;res=c-‘0‘;
13 while((c=getchar())>=‘0‘&&c<=‘9‘)res=res*10+c-‘0‘;res*=flag;
14 }
15
16 const int maxn = 2e3 + 5;
17 const int inf = 0x3f3f3f3f;
18
19 int n,m,e;
20 int vis[maxn][maxn];
21 int ask[maxn];
22 int cnt, ans;
23 int matched[maxn];
24 int in1[maxn], out1[maxn];//匹配后每个点出入度
25 int in[maxn], out[maxn];//匹配前每个点的出入度
26
27 bool fid(int x) {
28 for (int i = 1 ; i <= n; i++)
29 if (vis[x][i]) {
30 if (ask[i])
31 continue;
32 ask[i] = 1;
33 if (!matched[i] || fid(matched[i])) {
34 matched[i] = x ;
35 in1[i]++;
36 out1[x]++;
37 return true;
38 }
39 }
40 return false;
41 }
42
43 void match() {
44 cnt = 0;
45 memset(matched, 0, sizeof(matched));
46 for(int i = 1; i <= n; ++i) {
47 memset(ask, 0, sizeof(ask));
48 if(fid(i)) {
49 cnt++;
50 }
51 }
52 ans = cnt;
53 }
54
55
56
57 int main()
58 {
59 read(n); read(m);
60 cnt = 0;
61 for(int i = 1; i <= m; i++) {
62 int x,y;
63 read(x); read(y);
64 in[y]++;
65 out[x]++;
66 vis[x][y] = 1;
67 }
68 match();
69 // for ( int i = 1; i <= n; ++i ) {
70 // printf("match[%d]:%d\n",i, matched[i]);
71 // }
72 // puts("");
73 for ( int i = 1; i <= n; ++i ) {
74 //printf("out1[%d]:%d in1[%d]:%d\n",i, out1[i], i, in1[i]);
75 if(in[i] && !out[i]) {//T
76 if(in1[i] == 0) {
77 in1[i] = 1;
78 ++ans;
79 }
80 continue;
81 }
82 if(!in[i] && out[i]) {
83 if(out1[i] == 0) {
84 out1[i] = 1;
85 ++ans;
86 }
87 continue;
88 }
89 if(in[i] && out[i]) {
90 if(in1[i] == 0) {
91 ++ans;
92 in1[i] = 1;
93 }
94 if(out1[i] == 0) {
95 ++ans;
96 out1[i] = 1;
97 }
98 continue;
99 }
100 }
101 cout << m - ans << endl;
102 //printf("%d\n",ans);
103
104 return 0;
105 }
View Code
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long LL;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)flag=-1;res=c-‘0‘;
while((c=getchar())>=‘0‘&&c<=‘9‘)res=res*10+c-‘0‘;res*=flag;
}
const int maxn = 2e3 + 5;
const int inf = 0x3f3f3f3f;
int n,m,e;
int vis[maxn][maxn];
int ask[maxn];
int cnt, ans;
int matched[maxn];
int in1[maxn], out1[maxn];//匹配后每个点出入度
int in[maxn], out[maxn];//匹配前每个点的出入度
bool fid(int x) {
for (int i = 1 ; i <= n; i++)
if (vis[x][i]) {
if (ask[i])
continue;
ask[i] = 1;
if (!matched[i] || fid(matched[i])) {
matched[i] = x ;
in1[i]++;
out1[x]++;
return true;
}
}
return false;
}
void match() {
cnt = 0;
memset(matched, 0, sizeof(matched));
for(int i = 1; i <= n; ++i) {
memset(ask, 0, sizeof(ask));
if(fid(i)) {
cnt++;
}
}
ans = cnt;
}
int main()
{
read(n); read(m);
cnt = 0;
for(int i = 1; i <= m; i++) {
int x,y;
read(x); read(y);
in[y]++;
out[x]++;
vis[x][y] = 1;
}
match();
// for ( int i = 1; i <= n; ++i ) {
// printf("match[%d]:%d\n",i, matched[i]);
// }
// puts("");
for ( int i = 1; i <= n; ++i ) {
//printf("out1[%d]:%d in1[%d]:%d\n",i, out1[i], i, in1[i]);
if(in[i] && !out[i]) {//T
if(in1[i] == 0) {
in1[i] = 1;
++ans;
}
continue;
}
if(!in[i] && out[i]) {
if(out1[i] == 0) {
out1[i] = 1;
++ans;
}
continue;
}
if(in[i] && out[i]) {
if(in1[i] == 0) {
++ans;
in1[i] = 1;
}
if(out1[i] == 0) {
++ans;
out1[i] = 1;
}
continue;
}
}
cout << m - ans << endl;
//printf("%d\n",ans);
return 0;
}
