yesky wine供应系统题解【二分图匹配】

2022-03-28 11:06:04

4513: yesky wine供应系统

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 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

Sample Output

【样例输出1】
2
【样例输出2】
0

HINT

Source

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;
}