把每个实验看作二分图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
小阮 阅读(479)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法