把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。
1、从S向每个Xi连接一条容量为该点收入的有向边。
2、从Yi向T连接一条容量为该点支出的有向边。
3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。
统计出所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点，也就是最后一次增广找到阻塞流时能从S访问到的顶点。
其实也可以这样想，获得利润=收益-成本。而收益=总收益-损失收益（即由于没有选择某些项目所损失的收益）。那么：
获得利润=总收益-损失收益-成本，也就是获得利润=总收益-（损失收益+成本）。
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN = 100;
const int MAXM = MAXN*MAXN;
const int INF = 0x7FFFFFFF;
typedef struct edge
{
edge *next, *op;
int t, c;
}edge;
ifstream fin("shut.in");
ofstream fout("shut.out");
edge ES[MAXM], *V[MAXN], *P[MAXN], *Stae[MAXN];
int N, M, S, T, EC, Ans, Maxflow;
int level[MAXN], Stap[MAXN];
inline void addedge(int a, int b, int c){
ES[++EC].next=V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
ES[++EC].next=V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
V[a]->op=V[b]; V[b]->op=V[a];
}
void input(){
int a,i,c;
char ch;
fin>>M>>N;
S=0; T=N+M+1;
for (i=1;i<=M;i++){
fin>>c;
addedge(S,i,c);
Ans += c;
for (;;){
do{
ch=fin.get();
}while(ch==' ');
if(ch=='\n')break;
fin.putback(ch);
fin>>a;
addedge(i,a+M,INF);
}
}
for (i=1;i<=N;i++){
fin>>c;
addedge(i+M,T,c);
}
}
bool Dinic_level(){
int head,tail,i,j;
Stap[head=tail=0]=S;
memset(level,-1,sizeof(level));
level[S]=0;
while (head<=tail){
i=Stap[head++];
for (edge *e=V[i];e;e=e->next){
j=e->t;
if (e->c && level[j]==-1){
level[j] = level[i]+1;
if (j==T)
return true;
Stap[++tail] = j;
}
}
}
return false;
}
void Dinic_Augment(){
int i,j,delta,Stop;
memcpy(P, V, sizeof(edge*)*MAXN);
Stap[Stop=1]=S;
while (Stop){
i=Stap[Stop];
if (i!=T){
for (;P[i];P[i]=P[i]->next)
if (P[i]->c && level[i] + 1 == level[j=P[i]->t])
break;
if (P[i]){
Stap[++Stop] = j;
Stae[Stop] = P[i];
}else
Stop--,level[i]=-1;
}else{
delta = INF;
for (i=Stop;i>=2;i--)
if (Stae[i]->c < delta)
delta = Stae[i]->c;
Maxflow += delta;
for (i=Stop;i>=2;i--){
Stae[i]->c -= delta;
Stae[i]->op->c += delta;
if (Stae[i]->c==0)
Stop = i-1;
}
}
}
}
void Dinic(){
while (Dinic_level())
Dinic_Augment();
}
void output(){
for (int i=1;i<=M;i++)
if (level[i]!=-1)
fout<<i<<" ";
fout<<endl;
for ( i=M+1;i<=M+N;i++)
if (level[i]!=-1)
fout<<i-M<<" ";
fout<<endl;
Ans -= Maxflow;
fout<<Ans<<endl;
}
int main(){
input();
Dinic();
output();
return 0;
}posted on 2011-03-02 12:32
小阮 阅读(474)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法