hdu 4289 Control 夜

http://acm.hdu.edu.cn/showproblem.php?pid=4289

唉 本来对网络流的题目就不是很擅长 而且最近也没去碰这方面的题

结果这次有两个用最大流的  而且都是拆点的  伤不起呀

这个题把每个点拆成两个点 一个入点 一个出点 入点到出点流就为 所给费用 出点到入点流为 0 

对于相连的点 相互之间都是  I 点的出点到 J 点的入点流为最大 J 点的入点到 I 点的出点流为0

将 I 点和 J 点对换再建一次

最后Dinic

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

#define LL long long

//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int N=405;
const int M=200000;
const int INF=0x3f3f3f3f;
int head[N];
struct node
{
    int j,next;
    int f;
}side[M];
int I;
int L[N];
//int a[N];
queue<int>str;
int K;
int s,t;
void build(int i,int j,int f)
{
    side[I].j=j;
    side[I].f=f;
    side[I].next=head[i];
    head[i]=I++;
}
int bfs()
{
    memset(L,-1,sizeof(L));
    str.push(s);
    L[s]=0;
    while(!str.empty())
    {
        int x=str.front();str.pop();
        for(int t=head[x];t!=-1;t=side[t].next)
        {
            int l=side[t].j;
            if(L[l]==-1&&side[t].f>0)
            {
                L[l]=L[x]+1;
                str.push(l);
            }
        }
    }
    //cout<<L[K]<<endl;
    return L[K];
}
int dfs(int x,int sum)
{//cout<<sum<<endl;
    if(x==K)
    return sum;
    int temp=sum;
    for(int t=head[x];t!=-1;t=side[t].next)
    {
        int l=side[t].j;
        if(L[x]+1==L[l]&&side[t].f>0)
        {
            int w=dfs(l,min(temp,side[t].f));
            temp-=w;
            side[t].f-=w;
            side[t^1].f+=w;
        }
        if(temp==0)
        break;
    }
    //cout<<sum-temp<<endl;
    return (sum-temp);
}
int main()
{
    //freopen("data.txt","r",stdin);
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
       scanf("%d %d",&s,&t);
       memset(head,-1,sizeof(head));
       I=0;
       for(int i=1;i<=n;++i)
       {
           int a;
           scanf("%d",&a);
           build(i,i+n,a);
           build(i+n,i,0);
       }
       while(m--)
       {
           int i,j;
           scanf("%d %d",&i,&j);
           build(i+n,j,INF);
           build(j,i+n,0);
           build(j+n,i,INF);
           build(i,j+n,0);
       }
       K=t+n;
       int ans=0;
       while(bfs()!=-1)
       {
           int k;
           while(k=dfs(s,INF))
           ans+=k;
       }
       printf("%d\n",ans);
    }
    return 0;
}