|
|
Posted on 2010-10-02 22:20 成幸毅 阅读(224) 评论(0) 编辑 收藏 引用
实际上就是求最大权闭合图，还是比较容易的，没OJ交，就过了下样例。
 #include <iostream>
#include <queue>
using namespace std;
const int MAXN = 500;
const int INF = 0x3fffffff;
int n,m;
int s,t;
int d[MAXN];
int pre[MAXN];
int num[MAXN];
int exp[MAXN];
int instr[MAXN];
int cnt[MAXN];
int c[MAXN][MAXN];
  void ini_d(int s,int t)  {
memset(d,INF,sizeof(d));
memset(num,0,sizeof(num));
queue<int> Q;
Q.push(t);
d[t] = 0;
num[0] = 1;
int k ;
  while(!Q.empty()) {
k = Q.front();Q.pop();
for(int i = 0; i <= t ; i++) {
if(c[i][k] > 0 && d[i] > t) {
d[i] = d[k] + 1;
Q.push(i);
num[d[i]]++;
 }
}
}
 }
int findAlowArc(int i) {
int j;
for(j = 0; j < t + 1; j++) {
if(c[i][j] > 0 && d[i] == d[j] + 1) {
return j;
}
}
return -1;
}
int reLable(int i) {
int j;
int mm = INF;
for(j = 0; j < t +1; j++) {
if(c[i][j] > 0) mm = min(mm,d[j] + 1);
}
return mm == INF?t+1:mm;
}
int maxFlow(int s,int t) {
ini_d(s,t);
int flow = 0,i = s,j;
int delta;
memset(pre,-1,sizeof(pre));
while(d[s] <= t) {
j = findAlowArc(i);
if(j >= 0) {
pre[j] = i;
i = j;
if(i == t) {
delta = INF;
for(i = t; i != s; i = pre[i]) delta = min(delta,c[pre[i]][i]);
for(i = t; i != s; i = pre[i])
c[pre[i]][i] -= delta,c[i][pre[i]] += delta;
flow += delta;
}
}
else {
int x = reLable(i);
num[x]++;
num[d[i]]--;
if(num[d[i]] == 0) return flow;
d[i] = x;
if(i != s) i = pre[i];
}
}
return flow;
}
void dfs(int i) {
cnt[i] = 1;
for(int j = 0; j < t+1; j++) {
if(c[i][j] > 0 && !cnt[j]) {
dfs(j);
}
}
}
int main() {
while(scanf("%d%d",&n,&m) != EOF) {
int sum = 0;
int cost,u,v;
s = 0; t = n + m + 1;
memset(c,0,sizeof(c));
memset(exp,0,sizeof(exp));
memset(instr,0,sizeof(instr));
memset(cnt,0,sizeof(cnt));
for(int i = 1; i <= n; i++) {
scanf("%d%d%d",&cost,&u,&v);
sum += cost;
c[s][i] = cost;
c[i][u+n] = c[i][v+n] = INF;
exp[i] = 1;
instr[u] = instr[v] = 1;
}
for(int i = n+1; i <= m+n; i++) {
scanf("%d",&cost);
c[i][t] = cost;
}
int ans = maxFlow(s,t);
dfs(0);
for(int i = 1; i < t + 1; i++) {
if(cnt[i] == 1)
if(exp[i])
printf("%d ",i);
}
cout<<endl;
for(int i = 1; i < t + 1; i++) {
if(cnt[i] == 1)
if(instr[i])
printf("%d ",i);
}
cout<<endl;
printf("%d\n",sum - ans);
}
system("pause");
return 0;
}
|