HihoCoder 1398 网络流 - 最大权闭合子图

周末，小Hi和小Ho所在的班级决定举行一些班级建设活动。

根据周内的调查结果，小Hi和小Ho一共列出了N项不同的活动(编号1..N)，第i项活动能够产生a[i]的活跃值。

班级一共有M名学生(编号1..M)，邀请编号为i的同学来参加班级建设活动需要消耗b[i]的活跃值。

每项活动都需要某些学生在场才能够进行，若其中有任意一个学生没有被邀请，这项活动就没有办法进行。

班级建设的活跃值是活动产生的总活跃值减去邀请学生所花费的活跃值。

小Hi和小Ho需要选择进行哪些活动，来保证班级建设的活跃值尽可能大。

比如有3项活动，4名学生：

第1项活动产生5的活跃值，需要编号为1、2的学生才能进行；

第2项活动产生10的活跃值，需要编号为3、4的学生才能进行；

第3项活动产生8的活跃值，需要编号为2、3、4的学生才能进行。

编号为1到4的学生需要消耗的活跃值分别为6、3、5、4。

假设举办活动集合为{1}，需要邀请的学生集合为{1,2}，则得到的班级活跃值为5-9 = -4。

假设举办活动集合为{2}，需要邀请的学生集合为{3,4}，则得到的班级活跃值为10-9 = 1。

假设举办活动集合为{2,3}，需要邀请的学生集合为{2,3,4}，则得到的班级活跃值为18-12 = 6。

假设举办活动集合为{1,2,3}，需要邀请的学生集合为{1,2,3,4}，则得到的班级活跃值为23-18 = 5。

小Hi和小Ho总是希望班级活跃值越大越好，因此在这个例子中，他们会选择举行活动2和活动3。

输入

第1行：两个正整数N,M。1≤N≤200，1≤M≤200

第2行：M个正整数，第i个数表示邀请编号为i的学生需要花费的活跃值b[i]，1≤b[i]≤1,000

第3..N+2行：第i行表示编号为i的活动情况。首先是2个整数a,k，a表示该活动产生的活跃值，k表示该活动需要的学生人数。接下来k个整数列举该活动需要的学生编号。1≤a≤1,000，1≤k≤M

输出

第1行：1个整数，最大可以产生的班级活跃值

Sample Input

Sample Output

6
题解：最大权闭合子图裸题；

最大权闭合子图=正权点的和-最小割=正权点的和-最大流；(水题)
参考代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<queue>

 #include<vector>

 #include<stack>

 #include<map>

 #include<set>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 #define PI acos(-1.0)

 #define eps 1e-8

 #define mem(a,b) memset(a,b,sizeof a)

 const int INF=0x3f3f3f3f;

 const LL inf=0x3f3f3f3f3f3f3f3fLL;

 typedef pair<int,int> P;

 const int maxn=;

 int n,m,s,t,a,k,val;

 struct Edge{

     int from,to,cap,flow;

     Edge(int _f,int _t,int _c,int _fl):from(_f),to(_t),cap(_c),flow(_fl) { }

 };

 vector<Edge> edges;

 vector<int> G[maxn];

 bool vis[maxn];

 int d[maxn],cur[maxn];

 void Init()

 {

     mem(d,);

     for(int i=;i<=n;i++) G[i].clear();

 }

 void Addedge(int from,int to,int cap)

 {

     edges.push_back(Edge(from,to,cap,));

     edges.push_back(Edge(to,from,,));

     int m=edges.size();

     G[from].push_back(m-); G[to].push_back(m-);

 }

 bool bfs()

 {

     mem(vis,);

     queue<int> q;

     q.push(s);

     d[s]=;  vis[s]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();

         for(int i=;i<G[x].size();i++)

         {

             Edge &e=edges[G[x][i]];

             if(!vis[e.to] && e.cap>e.flow)

             {

                 vis[e.to]=;

                 d[e.to]=d[x]+;

                 q.push(e.to);

             }

         }

     }

     return vis[t];

 }

 int dfs(int x,int a)

 {

     if(x==t || a==) return a;

     int flow=,f;

     for(int &i=cur[x];i<G[x].size();++i)

     {

         Edge &e=edges[G[x][i]];

         if(d[e.to]==d[x]+ && (f=dfs(e.to,min(a,e.cap-e.flow)))>)

         {

             e.flow+=f;

             edges[G[x][i]^].flow-=f;

             flow+=f; a-=f;

             if(a==) break;

         }

     }

     return flow;

 }

 int Maxflow(int s,int t)

 {

     int flow=;

     while(bfs())

     {

         mem(cur,);

         flow+=dfs(s,INF);

     }

     return flow;

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin>>n>>m;

     int sum=,num;

     for(int i=;i<=m;i++) cin>>val,Addedge(n+i,m+n+,val);

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

     {

         cin>>val>>k;

         sum+=val;

         Addedge(,i,val);

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

         {

             cin>>num;

             Addedge(i,n+num,INF);

         }

     }

     s=,t=n+m+;

     int ans=sum-Maxflow(s,t);

     cout<<ans<<endl;

     return ;

 }

巴特西

HihoCoder 1398 网络流 - 最大权闭合子图

输入

输出

最新文章

热门文章