HDU 4971-A simple brute force problem【最大重み閉鎖図】

n(20)個の工事があり、各工事を完成して収益を得るのはp[i]、m(50)個の解決すべき難題であり、各難題を解決するのにかかる費用はc[i]である.
i番目のプロジェクトを完了するには、kiの問題、具体的な問題を解決する必要があります.
各難題の間には依存関係がある可能性があり、例えばi>jは問題jを解決するために問題iを解決する必要がある.(題名の説明に問題がありますが、例によっては前後が逆で、つまり題意という場所によって逆方向に図を建てればいいのです)
最大収益はいくらですか.
 
 
裸の最大権閉鎖図を比較し,最大権閉鎖図を解決するには一般的に最大流を用いる方法がある.
 
しかし訓練の時はこれを知らなかったので、終わってから関連資料を見て、
以下では、図面の作成方法についてのみ説明します.
 
ソース点Sを確立し、sは各工程点に1つのエッジを接続し、重み値はp[i]である.
1つのポイントTを確立し、tは各問題に1つのエッジを接続し、重み値はc[i]である.
次に、工事と完成工事に必要な解決の問題は、1つの辺につながって、重み値INF
難問の間は問題ごとにつながっており,重み値はINFのままである.
最大ストリームmaxflowを求める
答えはsigema(p[i])-maxflow
 
 

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<set>

#include<map>

#include<stack>

#include<vector>

#include<queue>

#include<string>

#include<sstream>

#define eps 1e-9

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define FOR(i,j,k) for(int i=j;i<=k;i++)

#define MAXN 1005

#define MAXM 40005

#define INF 0x3fffffff

#define PB push_back

#define MP make_pair

#define X first

#define Y second

#define lc (k<<1)

#define rc ((k<<1)1)

#define V(x) vector<x >

#define vs V(string)

#define vi V(int)

#define fr(x,y,z) for ((x)=(y);(x)<(z);(x)++)

#define fo(x,y) fr(x,0,y)

#define fir(n) fo(i,n)

#define fjr(n) fo(j,n)

#define fkr(n) fo(k,n)

#define fi fir(n)

#define fj fjr(n)

#define fk fkr(n)

#define pb push_back

#define sz size()

#define cs c_str()

#define clr(x,y) memset((x),(y),sizeof(x))

#define df double

using namespace std;

typedef long long LL;

int i,j,k,n,m,x,y,T,ans,big,cas,num,len;

bool flag;



const int inf = 0x3f3f3f3f;

struct edgenode

{

    int from,to,next;

    int cap;

}edge[MAXM];

int Edge,head[MAXN],ps[MAXN],dep[MAXN];



void add_edge(int x,int y,int c)

{

    edge[Edge].from=x;

    edge[Edge].to=y;

    edge[Edge].cap=c;

    edge[Edge].next=head[x];

    head[x]=Edge++;

    

    edge[Edge].from=y;

    edge[Edge].to=x;

    edge[Edge].cap=0;

    edge[Edge].next=head[y];

    head[y]=Edge++;

}



int dinic(int n,int s,int t)

{

    int tr,flow=0;

    int i,j,k,l,r,top;

    while(1){

        memset(dep,-1,(n+1)*sizeof(int));

        for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS  ，       

        {

            for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next)

            {

                if (edge[j].cap&&-1==dep[k=edge[j].to])

                {

                    dep[k]=dep[i]+1;ps[r++]=k;

                    if(k==t)

                    {

                        l=r;

                        break;

                    }

                }

            }

        }

        if(dep[t]==-1)break;

        

        for(i=s,top=0;;)//DFS   

        {

            if(i==t)//         

            {

                for(k=0,tr=inf;k<top;++k)

                    if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap;

                    

                for(k=0;k<top;++k)

                    edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr;

                    

                flow+=tr;

                i=edge[ps[top=l]].from;

            }

            

            for(j=head[i];j!=-1;j=edge[j].next)//          

                if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break;

                

            if(j!=-1)

            {

                ps[top++]=j;//         ，         

                i=edge[j].to;

            }

            else

            { 

                if (!top) break;//         ，   

                dep[i]=-1;

                i=edge[ps[--top]].from;

            }

        }

    }

    return flow;

}



int p[MAXN],c[MAXN],t;



int main()

{

    scanf("%d",&T);

    while (T--)

    {

        memset(head,-1,sizeof(head));

        Edge=0;

        scanf("%d%d",&n,&m);

        int sum=0;

        for (i=0;i<n;i++)

        {

            scanf("%d",&p[i]);

            add_edge(0,i+1,p[i]);

            sum+=p[i];

        }

        for (i=0;i<m;i++) 

        {

            scanf("%d",&c[i]);

            add_edge(n+1+i,n+m+1,c[i]);

        }

        for (i=0;i<n;i++)

        {

            scanf("%d",&k);

            //E[i].clear();

            for (j=0;j<k;j++)

            {

                scanf("%d",&t);

                add_edge(i+1,t+n+1,INF);

                //E[i].PB(t);

            }

        }

        

        for (i=0;i<m;i++)

        {

            for (j=0;j<m;j++)

            {

                scanf("%d",&t);

                if (t)

                {

                    add_edge(i+1+n,j+1+n,INF);

                }

            }

        }

        

        printf("Case #%d: %d
",++cas,sum-dinic(m+n+2,0,n+m+1));

        

    }

    return 0;

}