首页 > 代码库 > hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)

hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)

题目链接:http://hihocoder.com/problemset/problem/1394

 

代码:

技术分享
#include<bits/stdc++.h>using namespace std;const int N=505*2+10,M=20005,INF=0x3f3f3f3f;int n,m;int c[N][N],pre[N];int s,t;int bfs(){    memset(pre,0,sizeof(pre));    queue<int>q;    q.push(s);    pre[s]=1;    while(!q.empty())    {        int tmp=q.front();        q.pop();        for(int i=s+1;i<=t;i++)        {            if(pre[i]==0&&c[tmp][i]>0)            {                pre[i]=pre[tmp]+1;                q.push(i);            }        }    }    if(pre[t])    return 1;    return 0;}int dfs(int x,int f){    if(x==t||f==0)        return f;    int k=0,ans=0;    for(int i=1;i<=t;i++)    {        if(pre[i]==pre[x]+1&&c[x][i])        {            k=dfs(i,min(f,c[x][i]));            if(k)            {                ans+=k,f-=k;                c[x][i]-=k;                c[i][x]+=k;            }            if(f==0)                break;        }    }    return ans;}int maxflow(){    int ans=0;    while(bfs())    {        ans+=dfs(s,INF);    }    return n-ans;}int main(){    int u,v;    memset(c,0,sizeof(c));    scanf("%d%d",&n,&m);    s=0,t=n+1+n;    for(int i=0;i<m;i++)    {        scanf("%d%d",&u,&v);        c[u][v+n]=1;    }    for(int i=1;i<=n;i++)    {        c[0][i]=1;        c[i+n][n+1+n]=1;    }    printf("%d\n",maxflow());}
View Code

就是这个。我感觉我已经把原来在我心中的模板改成乱七八糟的了。、

说好听点是融合了,然而我总感觉会忘记一些东西。。。可怕

 

 

这题就是用网络流实现二分图匹配。

hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)