题意：n个项目（每个对应获得一定价值），m个技术问题（每个需要支出一定价值），每个项目必需要攻克若干个技术问题。技术难题之间有拓扑关系。

关键是建图。一看，第一感觉就是最大权闭合图，立即建好了图。不难：以项目为正权点，问题为负权点，有依赖关系的点边即可。

ps:这题题目有句话有问题，按样例的来！害我贡献一次WA.....

#include<iostream>#include<queue>#include<cstdio>#include<cstring>using namespace std;const int inf=0x3f3f3f3f;const int maxv=200,maxe=10000;int e[maxe][3];int head[maxv];int nume=0;void inline adde(int i,int j,int w){    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;    e[nume++][2]=w;    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;    e[nume++][2]=0;}int n,m,ss,tt;int vis[maxv];int  lev[maxv];bool bfs(){    for(int i=0;i<maxv;i++)       vis[i]=lev[i]=0;    queue<int>q;    q.push(ss);    vis[ss]=1;    while(!q.empty())    {        int cur=q.front();        q.pop();        for(int j=head[cur];j!=-1;j=e[j][1])        {            int v=e[j][0];            if(!vis[v]&&e[j][2]>0)            {                lev[v]=lev[cur]+1;                vis[v]=1;                q.push(v);            }        }    }    return vis[tt];}int dfs(int u,int minf){    if(u==tt||minf==0)return minf;    int sumf=0,f;    for(int j=head[u];j!=-1&&minf;j=e[j][1])    {        int v=e[j][0];        if(lev[v]==lev[u]+1&&e[j][2]>0)        {            f=dfs(v,minf<e[j][2]?minf:e[j][2]);            e[j][2]-=f;e[j^1][2]+=f;            sumf+=f;  minf-=f;        }    }    if(sumf==0)lev[u]=-1;    return sumf;}int dinic(){    int sum=0;    while(bfs())sum+=dfs(ss,inf);    return sum;}void init(){    nume=0;    for(int i=0;i<maxv;i++)      head[i]=-1;}int main(){    int T;    scanf("%d",&T);    for(int ii=1;ii<=T;ii++)    {        init();        scanf("%d%d",&n,&m);        ss=n+m;tt=ss+1; int sumz=0;        int aa,bb;        for(int i=0;i<n;i++)        {            scanf("%d",&aa);            adde(ss,i,aa);sumz+=aa;        }        for(int i=0;i<m;i++)        {            scanf("%d",&aa);            adde(i+n,tt,aa);        }        for(int i=0;i<n;i++)        {            scanf("%d",&aa);             while(aa--)             {                 scanf("%d",&bb);                 adde(i,bb+n,inf);             }        }          for(int i=0;i<m;i++)           for(int j=0;j<m;j++)           {               scanf("%d",&aa);               if(aa==1)               {                   adde(i+n,j+n,inf);               }           }      /*  for(int i=0;i<n+m+2;i++)           for(int j=head[i];j!=-1;j=e[j][1])           {               int v=e[j][0];               if(j%2==0)                 printf("%d->%d:%d\n",i,v,e[j][2]);           }*/         int ans=sumz-dinic();         printf("Case #%d: %d\n",ii,ans);    }    return 0;}

hdu 4971/ 2014多校/最大权闭合图