题目链接

题面：

4513: yesky wine供应系统
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 40 Solved: 9
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

题解：
该题我们有一个单源单汇的 DAG 图，从源点（酒厂）可以到达每个顶点，并从每个顶点可
以到达汇点（储藏站），目标是减少尽量多的边保持这个状态。因此，最后这个图的所有顶
点（除了源点和汇点）都至少有一条入边和一条出边，我们希望尽可能少的边达到目标。在
最理想的状况是我们对这些顶点只有 1 个入边，只有1个出边。因此我们需要找出尽可能多
的这样的顶点。这个我们可以用二分图的最大匹配来完成（把每个点拆成出度点 i 和入度点 i + n）。这样处理完后，有些顶点还没有入边或者出边，我们只需要任意给它添加上就可以了。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int mod=1000000007;
const double eps=1e-8;
const double dnf=1e20;
const double pi=acos(-1.0);
const int maxn=4100;
const int maxm=20100;
const int up=100;
const int maxp=1100;
int head[maxn],ver[maxm],edge[maxm],nt[maxm];
int d[maxn];
int n,m,s,t,tot=1;
queue<int>q;
  
  
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,nt[tot]=head[y],head[y]=tot;
}
  
bool bfs(void)
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();
  
    q.push(s);
    d[s]=1;
  
    while(q.size())
    {
        int x=q.front();
        q.pop();
  
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(edge[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return true;
            }
        }
    }
    return false;
}
  
int dinic(int x,int flow)
{
    if(x==t) return flow;
    int rest=flow ,k;
  
    for(int i=head[x];i&&rest;i=nt[i])
    {
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;
  
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
  
int getmaxx(void)
{
    int flow=0,maxflow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    return maxflow;
}
  
int main(void)
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y+n,1);
    }
    s=n*2+1,t=s+1;
    for(int i=1;i<=n;i++)
        add(s,i,1),add(i+n,t,1);
    int ans=getmaxx();
    for(int i=head[s];i;i=nt[i])
        if(edge[i]) ans++;
    for(int i=head[t];i;i=nt[i])
        if(!edge[i]) ans++;
    printf("%d\n",m-ans+2);
  
    return 0;
}