4513: yesky wine供应系统
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 34 Solved: 6
Description
自从上次懒羊羊红酒促销会后，越来越多的羊族及朋友喜欢上了yesky wine。懒羊羊跟叶老师申请要销售更多的yesky wine红酒。为此，他还准备改造他的红酒供应系统。红酒供应系统由一个酒厂，一个红酒储藏站，若干供应站和管道组成。当然，酒厂就位于叶老师所在的浙江理工大学后花园。中转站位于懒羊羊开设的很多酒吧、餐厅和其他红酒供应场所，需要时可以销售。红酒储藏站的位置非常神秘，不过这个对整个系统不是很重要。
红酒供应管道连接了刚才提到的各站点。酒厂至少连接了1个站点，神秘的储藏站也至少连接了一个站点。当然，极端的情况下，可能酒厂直接连接到神秘的储藏站，而没有其他任何中转站。
从酒厂出来的红酒通过管道充满了（经常是）一些站点并且能自动流到下一站点。
红酒在系统里流动，从某个站点流出的红酒不会返回到该站点，也就是说系统中不会出现回路。管道中酒的流向也是固定的不会回流。酒厂的酒是足够的，管道中的经常是有红酒流的。
现在的红酒供应系统有一些管道是多余的。你需要对这些管道进行优化，去掉一些多余的管道使得每个中转站都能得到红酒供应，同时也能流转到神秘的储藏站。当然，管道的容量是足够大的。
给你这个供酒系统的布置图，你能帮懒羊羊看看最多可以去掉多少根管道吗？
Input
第一行输入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个站点是独一无二的，也不会流向自己。只有一个站点是没有流进去的，那就是酒厂，也只有一个站点是没有流出的，那就是神秘的储藏站。
Output
输出一个整数，表示可以去掉多余的最大管道数
Sample Input
【样例输入1】 5 6 2 4 3 5 2 5 1 4 2 3 5 1 【样例输入2】 4 4 1 2 1 3 2 4 3 4
Sample Output
【样例输出1】 2 【样例输出2】 0
HINT
Source
思路
感觉这才是本场签到题，可惜被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 ",i, matched[i]); 71 // } 72 // puts(""); 73 for ( int i = 1; i <= n; ++i ) { 74 //printf("out1[%d]:%d in1[%d]:%d ",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 ",ans); 103 104 return 0; 105 }