程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3605Escape（縮點+網絡流之最大流）

HDU 3605Escape（縮點+網絡流之最大流）

編輯：C++入門知識

本來打算昨天寫兩道題的，結果這個題卡住了，最後才發現是最後的判斷條件出錯了，判斷滿流的條件應該是與n的比較，竟然寫成與所有星球總容量的比較了。（最近大腦短路。。）

這題也不是完全自己想的，沒想到縮點這一技巧，由於n的數據范圍太大，普通的建圖方法會超時超內存，需要縮點，因為對於每個點來說，一共只有2^10種方法，而最多一共有10W個點，顯然有很多點是重復的，這時可以采取縮點的方法，將重復的當成一個點來處理。這樣數據范圍就縮小到了1024個點，速度大大提升。

建圖思路是建一源點與匯點，將每種方法與源點相連，權值為這種方法重復的次數，將每個星球與匯點相連，權值為每個星球的最大容量，再將每種方法與星球相連，權值為INF，最後判斷是否滿流。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 

using namespace std;
const int INF=1e9;
int head[2000], s, t, nv, n, cnt;
int num[2000], d[2000], pre[2000], cur[2000], q[2000], fei[2000];
struct node
{
    int u, v, next, cap;
}edge[1000000];
void add(int u, int v, int cap)
{
    edge[cnt].v=v;
    edge[cnt].cap=cap;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].cap=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void bfs()
{
    memset(num,0,sizeof(num));
    memset(d,-1,sizeof(d));
    int f1=0, f2=0, i;
    q[f1++]=t;
    d[t]=0;
    num[0]=1;
    while(f1>=f2)
    {
        int u=q[f2++];
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(d[v]==-1)
            {
                d[v]=d[u]+1;
                num[d[v]]++;
                q[f1++]=v;
            }
        }
    }
}
int isap()
{
    memcpy(cur,head,sizeof(cur));
    int flow=0, i, u=pre[s]=s;
    bfs();
    while(d[s]edge[cur[i]].cap)
                {
                    f=edge[cur[i]].cap;
                    pos=i;
                }
            }
            for(i=s;i!=t;i=edge[cur[i]].v)
            {
                edge[cur[i]].cap-=f;
                edge[cur[i]^1].cap+=f;
            }
            flow+=f;
            if(flow>=n)
                return flow;
            u=pos;
        }
        for(i=cur[u];i!=-1;i=edge[i].next)
        {
            if(d[edge[i].v]+1==d[u]&&edge[i].cap)
            {
                break;
            }
        }
        if(i!=-1)
        {
            cur[u]=i;
            pre[edge[i].v]=u;
            u=edge[i].v;
        }
        else
        {
            if(--num[d[u]]==0) break;
            int mind=nv;
            for(i=head[u];i!=-1;i=edge[i].next)
            {
                if(mind>d[edge[i].v]&&edge[i].cap)
                {
                    mind=d[edge[i].v];
                    cur[u]=i;
                }
            }
            d[u]=mind+1;
            num[d[u]]++;
            u=pre[u];
        }
    }
    return flow;
}
int main()
{
    int m, x, i, j, top, y, z, num, a[20];
    while(scanf(%d%d,&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(fei,0,sizeof(fei));
        cnt=0;
        s=0;
        top=0;
        num=0;
        for(i=1;i<=n;i++)
        {
            x=0;
            for(j=1;j<=m;j++)
            {
                scanf(%d,&y);
                x=x*2+y;
            }
            fei[x]++;
        }
        for(i=1;i<=1100;i++)
        {
            if(fei[i])
            {
                num++;
            }
        }
        t=num+m+1;
        nv=t+1;
        for(i=1;i<=1100;i++)
        {
            if(fei[i])
            {
                //printf(--%d %d
, i, fei[i]);
                top++;
                add(s,top,fei[i]);
                x=i;
                z=m+1;
                while(x)
                {
                    y=x%2;
                    z--;
                    if(y)
                    {
                        add(top,z+num,INF);
                    }
                    //printf(--%d %d %d %d--,y, top, z, num);
                    x=x/2;
                }
                //printf(
);
            }
        }
        for(i=1;i<=m;i++)
        {
            scanf(%d,&x);
            add(i+num,t,x);
        }
        x=isap();
        if(x>=n)
            printf(YES
);
        else
            printf(NO
);
    }
    return 0;
}