2018 中国大学生程序设计竞赛宁夏网络赛clever king

文章转载自：xuanqis.com

题目链接：计蒜客

Description:

In order to increase the happiness index of people's lives, King Y has decided to develop the manufacturing industry vigorously. There are total n kinds of products that King can choose to produce, different products can improve the happiness index of poeple's lives in different degrees, of course, the production of goods needs raw materials, different products need different ore or other products as raw materials. There are total m mines, and each mine can exploit different ore, Therefore, there are m types of ores, the cost of each mining for each mine is different, king Y want to maximize the income, the calculation method of income is:∑increased happiness index - ∑mining costs. If you choose to exploit a mine, there will be an unlimited number of this kind of ore. What's more, if you produce one product, the happiness index will definitely increase, no matter how many you produce.

Input:

The first line of the input has an integer T(1<=T<=50), which represents the number of test cases. In each test case, the first line of the input contains two integers n(1<=n<=200)--the number of the products and m(1<=m<=200)--the number of mines. The second line contains n integers, val[i] indicates the happiness index that number i product can increase. The third line contains m integers, cost[i] indicates the mining cost of number i mine. The next n lines, each line describes the type of raw material needed for the number i product, in each line, the first two integers n1(1<=n1<=m)--the number of ores that this product needs, n2(1<=n2<=n)--the number of products that this product needs, the next n1 + n2 integers indicate the id of ore and product that this product needs. it guarantees that ∑n1+∑n2<=2000.

Output:

Each test case output an integer that indicates the maximum value ∑val[i]-∑cost[i].

忽略每行输出的末尾多余空格

样例输入

2 3 3 600 200 400 100 200 300 1 2 1 2 3 1 0 2 1 0 3 3 4 600 400 200 100 200 300 1000 2 1 1 2 3 1 0 1 1 0 1

样例输出

600 900

题意：

有n种产品，m种矿，生产产品要用到矿或者其他的产品，开采一种矿有花费，但是花费的是定值，生产产品出来得到的也是定值，就是说开采的矿不管你用多少，都只要一次的钱（其实是幸福值），生产出产品也只有一次的钱。要求算出所能得到的最大值。

思路：

最大权闭合子图问题，设置一个超级源点，超级汇点。从源点到每个产品建一条边，边的权值为产品的值，从矿到汇点建立一条边，边的权值是矿消耗的值。问题就转化为所有的产品总值减去最小割的值。对最大权闭合子图不懂的可以参考胡伯涛的最小割模型在信息学竞赛中的应用。

代码：

 

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define pa pair<int,int> #define maxn 60000 #define maxm 320000 #define inf 1000000000 using namespace std; struct edge_type { int next,to,v; }e[maxm]; int head[maxn],cur[maxn],dis[maxn]; int n,m,s,t,cnt=1,ans=0,x,y,z; inline int read() //读入一个整数 { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} //f记录正负号 while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add_edge(int x,int y,int v) //添加一条边，应该说两条边，正反两条 { e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt; e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt; } inline bool bfs() //返回的是是否存在从源点到汇点的流 { queue<int>q; memset(dis,-1,sizeof(dis)); dis[s]=0;q.push(s); while(!q.empty()) { int tmp=q.front();q.pop(); if (tmp==t) return true; for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1) //下一个点没访问过 { dis[e[i].to]=dis[tmp]+1; //距源点的距离 q.push(e[i].to); } } return false; } inline int dfs(int x,int f) //深搜以得到一条从源点到汇点的流，返回的流的值 { int tmp,sum=0; if (x==t) return f; //已经到终点了 for(int &i=cur[x];i;i=e[i].next) { int y=e[i].to; if (e[i].v&&dis[y]==dis[x]+1) { tmp=dfs(y,min(f-sum,e[i].v)); e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp; //这里开始的时候弄了正反边，cnt从2开始 if (sum==f) return sum; } } if (!sum) dis[x]=-1; //这条路不用走了，走不通了 return sum; } inline void dinic() //dinic算法求 { while (bfs()) //存在从源到汇的流 { F(i,1,t) cur[i]=head[i]; ans-=dfs(s,inf); } } void init(){ //进行初始化 memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); ans =0; cnt=1; } int main() { freopen("1.txt", "r", stdin); int num; num=read(); while(num--){ init(); n=read();m=read(); //输入n个产品，m个矿 s=n+m+1;t=s+1; //超级源点，超级汇点 F(i,1,n) { z=read(); ans+=z; add_edge(s,i,z); //对于每个盈利的，与源点连一条边 } F(i,1,m) { z=read(); add_edge(i+n,t,z); //对于每个花钱的，与汇点连一条边 } int numa,numb; F(i,1,n){ numa=read(); numb=read(); F(j,1,numa){ y=read(); add_edge(i,y+n,inf); } F(j,1,numb){ y=read(); add_edge(i,y,inf); } } dinic(); printf("%d",ans); if(t!=1)printf("\n"); } }