学步园

http://blog.csdn.net/ipqhjjybj/article/details/9172347

不说什么啦。。。这个直接是套模板的，就是前期优化了一点点，把重复边都合并了，效率提升挺明显的。 从472MS提高到了62MS，后来将 memset(a,0,sizeof(a));这样的写法改成了memset(a,0,(n+1)*sizeof(int));  时间从 62MS 调高到了46MS。。。 感觉同为O(mn^2)的SAP与DINIC算法，感觉数据量在n <= 15,M<=1000时（边重复的合并了），效率差别不大。好佩服那些过此题时，时间是10MS的大牛。真是优化到了极致。

而且发现 int 申请 二维数组时，时间开销也是有点大的,也不枉费我一道题交了10来次了。。

最后。。直接附上模板

#include <stdio.h>
#include <string.h>
const int maxn=20;
const int maxm=1005;
const int inf=1<<30;

struct edge
{
    int from,to,val,next;
}map[maxm];
int vis[maxn],que[maxn],dist[maxn],len;
int MAP[maxn][maxn];
int n,m;
void init()
{
    len=0;
    memset(vis,-1,(n+1)*sizeof(int));
 }
 void insert (int from,int to,int val)
 {
     map[len].from=from;
     map[len].to=to;
     map[len].val=val;
     map[len].next=vis[from];
     vis[from]=len++;

     map[len].from=to;
     map[len].to=from;
     map[len].val=0;
     map[len].next=vis[to];
     vis[to]=len++;
 }

int Dinic(int n,int s,int t)
{
    int ans=0;
    while(true)
    {
        int head,tail,id,i;
        head=tail=0;
        que[tail++]=s;
        memset(dist,-1,(n+1)*sizeof(int));
        dist[s]=0;
        while(head<tail)
        {
            id=vis[que[head++]];
            while(id!=-1)
            {
                if(map[id].val>0&&dist[map[id].to]==-1)
                {
                    dist[map[id].to]=dist[map[id].from]+1;
                    que[tail++]=map[id].to;
                    if(map[id].to==t)
                    {
                        head=tail;
                        break;
                    }
                }
                id=map[id].next;
            }
        }
        if(dist[t]==-1)
            break;
        id=s,tail=0;
        while(true)
        {
            if(id==t)
                //找到一条增广路
            {
                int flow=inf,fir;
                for(i=0;i<tail;i++)
                    if(map[que[i]].val<flow)
                    {
                        fir=i;
                        flow=map[que[i]].val;
                     }
                    for(i=0;i<tail;i++)
                    {
                        map[que[i]].val-=flow;
                        map[que[i]^1].val+=flow;
                    }
                    ans+=flow;
                    tail=fir;
                    id=map[que[fir]].from;
             }
            id=vis[id];
            while(id!=-1)
            {
                if(map[id].val>0&&dist[map[id].from]+1==dist[map[id].to])
                    break;
                id=map[id].next;
             }
            if(id!=-1)
            {
                que[tail++]=id;
                id=map[id].to;
             }
            else
            {
                if(tail==0)
                    break;
                dist[map[que[tail-1]].to]=-1;
                id=map[que[--tail]].from;
             }
         }
     }
    return ans;
 }

int main()
{
  //  freopen("3549.in","r",stdin);
    int t;
    int i;
    int s,e,a;
    int tt=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        init();
        memset(MAP,0,sizeof(MAP));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&s,&e,&a);
            MAP[s][e]+=a;
            //insert(s,e,a);
        }
        for(int i = 0;i <= n;i++)
            for(int j = 0;j <= n;j++)
                if(MAP[i][j]&&i!=j)
                    insert(i,j,MAP[i][j]);
        printf("Case %d: %d\n",++tt,Dinic(n,1,n));
    }

    return 0;
}