HDOJ4322-費用流

/*
好題~
網絡流不熟啊，
剛開始枚舉會被當成喜歡的糖的糖的組合來最大流,确實沒有考慮清楚當bi%k的一些不同的情況~
看了一篇比較有啟發的部落格後，才寫的費用流：

以糖果數量限制流量,在喜歡的糖果與人之間連邊
 在人與彙點間建費用為k,流量為b[i]/k的邊，那麼cost*flow就成了glad value了!(這是我茅塞頓開的地方)
 那麼我在之前用最大流做時不能處理的b[i]%k的問題也好解決了:
     當b[i]%k==0時,不用管他,
     當b[i]%k==1時,多出來的必選的糖喜不喜歡無所謂,也不用管,
     當b[i]%k>1時,我們應盡量去選喜歡的糖,此時加一條邊(i,T,1,b[i]%k);就行了。
最後我們求得的最大費用為各人選擇喜歡的糖所産生的glad value總值,最大流為選擇的喜歡的糖果的數量，是以max_cost+(n-max_flow)>b1+b2+...+bm就是YES了!
 當然這裡應該求的是最大費用最大流。
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int NN=100;
const int MM=1000;
const int INF=0x3fffffff;

int n,m,k,sum,cnt,a,S,T,NV,b[NN],like[NN][NN];

struct Edge
{
    int u,v,f,c,next;
} e[MM];
int en,head[NN];
void add(int u,int v,int f,int c)
{
    e[en].u=u;
    e[en].v=v;
    e[en].f=f;
    e[en].c=c;
    e[en].next=head[u];
    head[u]=en++;
    e[en].u=v;
    e[en].v=u;
    e[en].f=0;
    e[en].c=-c;
    e[en].next=head[v];
    head[v]=en++;
}

void build()
{
    S=0;
    T=n+m+1;
    NV=T+1;
    en=0;
    for (int i=0; i<NV; i++) head[i]=-1;

    for (int i=1; i<=n; i++) add(S,i,1,0);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (like[j][i]) add(i,j+n,1,0);
    for (int j=1; j<=m; j++)
    {
        add(j+n,T,b[j]/k,k);
        if (b[j]%k>1) add(j+n,T,1,b[j]%k);
    }
}

bool used[NN];
int dis[NN],p[NN];
bool SPFA(void)
{
    queue<int> q;
    for (int i=1; i<NV; i++) dis[i]=-INF;
    dis[S]=0;
    q.push(S);
    p[S]=-1;
    while (!q.empty())
    {
        int u=q.front();
        used[u]=false;
        q.pop();
        for (int i=head[u]; i!=-1; i=e[i].next)
        {
            int v=e[i].v;
            if (e[i].f>0 && dis[v]<dis[u]+e[i].c)
            {
                dis[v]=dis[u]+e[i].c;
                p[v]=i;
                if (!used[v])
                {
                    used[v]=true;
                    q.push(v);
                }
            }
        }
    }
    if (dis[T]==-INF) return false;
    else return true;
}

bool MCMF()
{
    build();
    int max_flow=0;
    int max_cost=0;
    while (SPFA())
    {
        int u,v;
        for (v=T; p[v]!=-1; v=u)
        {
            u=e[p[v]].u;
            e[p[v]].f-=1; //新産生的流量總是1
            e[p[v]^1].f+=1;
        }
        max_flow++;
        max_cost+=dis[T];
    }
    if (max_cost+n-max_flow>=sum) return true;
    else return false;
}

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        sum=0;
        for (int i=1; i<=m; i++)
        {
            scanf("%d",&b[i]);
            sum+=b[i];
        }
        for (int i=1; i<=m; i++)
            for (int j=1; j<=n; j++) scanf("%d",&like[i][j]);

        printf("Case #%d: ",++cas);
        if (k<=1)
        {
            if (n>=sum) printf("YES\n");
            else        printf("NO\n");
            continue;
        }
        if (n>=sum)
        {
            printf("YES\n");
            continue;
        }
        if (n*k<sum)
        {
            printf("NO\n");
            continue;
        }
        if (MCMF()) printf("YES\n");
        else        printf("NO\n");
    }
    return 0;
}