NKOJ 2439 四叶草魔杖（最小生成树+状压dp/网络流）

发表于 |
字数统计: 1,461字 | 阅读时长 ≈ 7min

2439 四叶草魔杖

问题描述
　　
　　 魔杖护法Freda融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻发着淡淡的七色光。圣剑护法rainbow取出了一个圆盘，圆盘上镶嵌着N颗宝石，编号为0~N-1。第i颗宝石的能量是Ai。如果Ai>0，表示这颗宝石能量过高，需要把Ai的能量传给其它宝石；如果Ai<0，表示这颗宝石的能量过低，需要从其它宝石处获取-Ai的能量。保证∑Ai =0。只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自然之界的通道。
不过，只有M对宝石之间可以互相传递能量，其中第i对宝石之间无论传递多少能量，都要花费Ti的代价。探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都相同?

输入格式

第一行两个整数N、M。
第二行N个整数Ai。
接下来M行每行三个整数pi,qi,Ti，表示在编号为pi和qi的宝石之间传递能量需要花费Ti的代价。数据保证每对pi、qi最多出现一次。

输出格式

输出一个整数表示答案。无解输出Impossible

样例输入

3 3
50 -20 -30
0 1 10
1 2 20
0 2 100

样例输出

30

提示

对于 50% 的数据，2<=N<=8。
对于 100% 的数据，2<=N<=16，0<=M<=N*(N-1)/2，0<=pi,qi<N，-1000<=Ai<=1000，0<=Ti<=1000，∑Ai=0。

做法一：最小生成树+状压dp

枚举点集，若当前点集构成联通块且能量之和为0，显然当前联通块传递能量的最小代价是其最小生成树，因此将每个这样的联通块看成一个物品，背包dp算出最小费用即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{int x,y,z;};
bool cmp(node a,node b)
{return a.z<b.z;}
int n,m,A[20],S[66666],V[66666],F[66666],TOT;
int fa[20];
bool mark[20];
node P[200];
int GF(int x)
{
	if(fa[x]!=x)fa[x]=GF(fa[x]);
	return fa[x];
}
int Kruscal(int s)
{
	int i,j,fx,fy,x,y,k=1,tot=0,cnt=0,ans=0;
	memset(mark,0,sizeof(mark));
	for(i=1;i<=n;i++)if((1<<i-1)&s)tot++,mark[i]=1;
	for(i=1;i<=n;i++)fa[i]=i;
	while(k<=m&&cnt<tot)
	{
		x=P[k].x;
		y=P[k].y;
		fx=GF(x);fy=GF(y);
		if(mark[x]&&mark[y]&&fx!=fy)
		{
			ans+=P[k].z;
			fa[fx]=fy;
			cnt++;
		}
		k++;
	}
	if(cnt+1<tot)return 1e9;
	return ans;
}
int main()
{
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].z);
		P[i].x++;P[i].y++;
	}
	sort(P+1,P+m+1,cmp);
	TOT=(1<<n)-1;
	for(i=1;i<=TOT;i++)
	for(j=1;j<=n;j++)if((1<<j-1)&i)S[i]+=A[j];
	for(i=1;i<=TOT;i++)if(S[i]==0)V[i]=Kruscal(i);
	for(i=1;i<=TOT;i++)F[i]=1e9;F[0]=0;
	for(i=0;i<=TOT;i++)
	{
		if(S[i])continue;
		for(j=0;j<=TOT;j++)F[i|j]=min(F[i|j],F[j]+V[i]);
	}
	if(F[TOT]==1e9)puts("Impossible");
	else cout<<F[TOT];
}

做法二：网络流

建图比较简单，从源点向每个$A[i]>0$的点连边，容量为$A[i]$，费用为0，从每个$A[i]<0$的点向汇点连边，容量为$-A[i]$，费用为0，然后点之间的边容量设为无穷。需要注意的是与普通的费用流不同，每次找到一条路时，要将有流经过的边费用改成0，将没有流经过的边费用改成原值，双向边都要改，因为第二次走是不产生费用的。最后再将有流的边的费用加起来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<deque>
#define N 123
#define M 1234
using namespace std;
int qg=0,n,m,S,T,A[123];
int TOT=1,LA[N],EN[M],NE[M],G[M],W[M],F[M];
int dis[N],use[N],pre[N],maxflow,mincost;
bool mark[N];
queue<int>Q;
void ADD(int x,int y,int w,int c)
{
	TOT++;
	EN[TOT]=y;
	G[TOT]=w;
	F[TOT]=c;
	W[TOT]=c;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
bool FP()
{
	int i,x,y;
	memset(dis,60,sizeof(dis));
	dis[S]=0;mark[S]=1;Q.push(S);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		mark[x]=0;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(G[i]&&dis[y]>dis[x]+W[i])
			{
				dis[y]=dis[x]+W[i];
				pre[y]=x;use[y]=i;
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
	if(dis[T]!=dis[0])return 1;
	return 0;
}
void AF()
{
	int f=1e9,i;
	for(i=T;i!=S;i=pre[i])f=min(f,G[use[i]]);
	maxflow+=f;
	for(i=T;i!=S;i=pre[i])
	{
		G[use[i]]-=f;
		G[use[i]^1]+=f;
		if(G[use[i]]!=1e9)W[use[i]^1]=W[use[i]]=0;
		else
		{
			W[use[i]]=F[use[i]];
			W[use[i]^1]=F[use[i]^1];
		}
	}
}
int main()
{
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	S=n+1;T=S+1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&A[i]);
		if(A[i]>0)
		{
			ADD(S,i,A[i],0);
			ADD(i,S,0,0);
			qg+=A[i];
		}
		else 
		{
			ADD(i,T,-A[i],0);
			ADD(T,i,0,0);
		}
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x++;y++;
		ADD(x,y,1e9,z);
		ADD(y,x,1e9,z);
	}
	while(FP())AF();
	if(maxflow!=qg)puts("Impossible");
	else
	{
		for(i=2;i<=TOT;i++)
		if(G[i]&&G[i]!=1e9)mincost+=F[i];
		cout<<mincost/2;
	}
}