HDU 3549 Flow Problem 最大流 最小增廣路 DINIC算法 也是46MS

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;
}