网络流模版题

曾经在去年救过我省选的题,感谢周植

题意:有n个城市,第i个城市里一开始有a_i个人

后来,有些人往某个相邻的城市走(只走一次),之后,第i个城市有b_i个人

求是否有可能,如果可能,输出方案数,也就是说第i个城市有几个人往第j个城市走(i=j则表示没走的人)

这真的是网络流..不是最小割..

第i个城市向第j个连边,然后流一遍..求最大流..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105],b[105];
int ans[105][105];
const int maxn=505;
const int inf=99999999;
struct edge
{
    int y;
    int weight;
    edge * next;
    edge * anti;
};
edge * li[1005];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
edge * inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
    return t;
}
void insert_edge(int x,int y,int z)
{
    edge * t1=inserts(x,y,z);
    edge * t2=inserts(y,x,0);
    t1->anti=t2;
    t2->anti=t1;
}
int dis[maxn];
bool bfs(int s,int t)
{
    static int que[maxn];
    int front=0,rail=1;
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    que[0]=s;
    for (;front<rail;front++)
    {
        int now=que[front];
        edge * x;
        for (x=li[now];x!=0;x=x->next)
        {
            if ((dis[x->y]==-1)&&(x->weight!=0))
            {
                dis[x->y]=dis[now]+1;
                if (x->y==t) return true;
                que[rail++]=x->y;
            }
        }
    }
    return false;
}
int max_flow(int s,int t)
{
    int tot=0;
    for (;bfs(s,t);)
    {
        static int pre[maxn];
        static edge * cur[maxn];
        static edge * path[maxn];
        memcpy(cur,li,sizeof(cur));
        int now=s;
        for (;dis[s]!=-1;)
        {
            if (now==t)
            {
                int temp;
                int mini=inf;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    mini=min(mini,path[temp]->weight);
                }
                tot+=mini;
                for (temp=t;temp!=s;temp=pre[temp])
                {
                    path[temp]->weight-=mini;
                    path[temp]->anti->weight+=mini;
                }
                now=s;
            }
            edge * x;
            for (x=li[now];x!=0;x=x->next)
            {
                if ((x->weight!=0)&&(dis[x->y]==dis[now]+1))
                {
                    pre[x->y]=now;
                    path[x->y]=x;
                    cur[now]=x;
                    now=x->y;
                    break;
                }
            }
            if (x==0)
            {
                dis[now]=-1;
                now=pre[now];
            }
        }
    }
    return tot;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    int sum_a=0;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum_a+=a[i];
    }
    int sum_b=0;
    for (i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        sum_b+=b[i];
    }
    if (sum_a!=sum_b)
    {
        printf("NO\n");
        return 0;
    }
    int s=n*2,t=n*2+1;
    for (i=0;i<n;i++)
    {
        insert_edge(s,i,a[i]);
    }
    for (i=0;i<n;i++)
    {
        insert_edge(i+n,t,b[i]);
        insert_edge(i,i+n,inf);
    }
    for (i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y+n,inf);
        insert_edge(y,x+n,inf);
    }
    int val=max_flow(s,t);
    if (val!=sum_a)
    {
        printf("NO\n");
    }
    else
    {
        printf("YES\n");
        for (i=0;i<n;i++)
        {
            edge * x;
            for (x=li[i+n];x!=0;x=x->next)
            {
                if (x->y==t) continue;
                ans[x->y][i]+=x->weight;
            }
        }
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<n;j++)
            {
                printf("%d ",ans[i][j]);
            }
            printf("\n");
        }
        return 0;
    }
    return 0;
}