[Cogs727] [网络流24题#2] 太空飞行计划 [网络流，最小割]

建图：源点—(w[i])—>实验—(∞)—>仪器—(cost[i])—>汇点，

如果该实验造成收益，则仪器到汇点的边在最小割中，

如果该实验造成损失，则源点到实验的边在最小割中，

故答案就是所有实验的所有收益（不考虑仪器花费的）减去最小割。

特别注意，最后统计方案时，不能直接判断边权是否为0，因为当花费等于收益时，这种方法会将该实验计入答案而题目则不允许，故应该在最后Bfs出的level数组中判断是否可达，再通过实验把所需仪器统计出来。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <ctime>

 #include <algorithm>

 #include <queue>

 #include <vector>

 using namespace std;

 template<const int _n>

 struct Edge

 {

     struct Edge_base { int    to,next,w; }e[_n];

     int    p[_n],cnt;

     Edge()    { clear(); }

     inline int    start(const int x) { return p[x]; }

     inline void    insert(const int x,const int y,const int z)

     { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }

     inline Edge_base&    operator[](const int x) { return e[x]; }

     inline void    clear() { cnt=,memset(p,,sizeof(p)); }

 };

 int    n,m,SSS,TTT;

 int    w[],cost[];

 int    level[],cur[];

 char    str[];

 Edge<>    e;

 vector<pair<int,int> >    vec;

 bool    Bfs(const int S)

 {

     int    i,t;

     queue<int>    Q;

     memset(level,,sizeof(int)*(n+m+));

     level[S]=;Q.push(S);

     while(!Q.empty())

     {

         t=Q.front(),Q.pop();

         for(i=e.start(t);i;i=e[i].next)

         {

             if(!level[e[i].to] && e[i].w)

             {

                 level[e[i].to]=level[t]+;

                 Q.push(e[i].to);

             }

         }

     }

     return    level[TTT];

 }

 int    Dfs(const int S,const int bk)

 {

     if(S==TTT)return bk;

     int    rest=bk;

     for(int &i=cur[S];i;i=e[i].next)

     {

         if(level[e[i].to]==level[S]+ && e[i].w)

         {

             int    flow=Dfs(e[i].to,min(rest,e[i].w));

             e[i].w-=flow;

             e[i^].w+=flow;

             if((rest-=flow)<=)break;

         }

     }

     if(rest==bk)level[S]=;

     return bk-rest;

 }

 int    Dinic()

 {

     int    i,j,flow=;

     int    Ans[]={};

     while(Bfs(SSS))

     {

         memcpy(cur,e.p,sizeof(int)*(n+m+));

         flow+=Dfs(SSS,0x3f3f3f3f);

     }

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

     {

         if(level[i])

         {

             printf("%d ",i);

             for(j=e.start(i);j;j=e[j].next)

                 Ans[e[j].to-n]=;

         }

     }

     printf("\n");

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

     {

         if(Ans[i])printf("%d ",i);

     }

     printf("\n");

     return flow;

 }

 void    Build()

 {

     int    i;

     SSS=n+m+,TTT=n+m+;

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

     {

         e.insert(SSS,i,w[i]);

         e.insert(i,SSS,);

     }

     for(i=;i<(int)vec.size();++i)

     {

         e.insert(vec[i].first,vec[i].second+n,0x3f3f3f3f);

         e.insert(vec[i].second+n,vec[i].first,);

     }

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

     {

         e.insert(i,TTT,cost[i-n]);

         e.insert(TTT,i,);

     }

     return ;

 }

 #define    EOL    -1

 int    getint(int&    data,int & t)

 {

     char    ch;data=;

     ch=str[t++];

     while((ch<'' || ch>'') && ch)ch=str[t++];

     while(ch>='' && ch<='')data=data*+ch-,ch=str[t++];

     if(!data)return EOL;

     return ;

 }

 int main()

 {

     freopen("shuttle.in","r",stdin);

     freopen("shuttle.out","w",stdout);

     int    i,c,Sum=;

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

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

     {

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

         Sum+=w[i];

         fgets(str,,stdin);

         int t=;

         while(~getint(c,t))

         {

             vec.push_back(make_pair(i,c));

             if(t==-)break;

         }

     }

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

     {

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

     }

     Build();

     printf("%d\n",Sum-Dinic());

     return ;

 }