Tang-Dreamoon's Blog

bzoj 1927 星际竞速

发表于 | 分类于 ， ，

源汇补充

　　题目链接：bzoj 1927

　　题意：写bzoj的题意就是简单——题意见上……

　　题解：感觉上显然是一个最小费用最大流。首先我们得让每一个点经过且仅经过一次，所以我们用最大流为 N 来限制每个点都要经过一次。然后拆点，从源点向每一个点的入点连边费用为定位时间，对于（ U , V ）从 U 的出点向 V 的入点连边费用为边权，每个点的出点再向汇点连边容量为 1。然后我们就会发现一个尴尬的事情，为了使最大流为 N 这种构图方式将不会走点和点之间的边。也就是说每个流入点的流都流向汇点而损失掉了。所以我们改变一下每个点和汇点的连接方式。我们让每个点的入点向汇点连一条容量为 1 的边，这样当有一股流流进这个点的时候就将会流向汇点。如何补充这一股损失掉的流呢？我们再从源点向每一个点的出点连一条容量为 1，费用为 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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int s,t;
int tot=0;
struct table{
	int to,id,val;
};
vector<table> ve[8888];
int dis[8888],where[8888],mina[8888],from[8888];
int f[300000];
bool vis[8888];
int min(int a,int b)
{
	return a < b ? a : b;
}
bool spfa()
{
	memset(dis,0x3f,sizeof(dis));
	memset(mina,0x3f,sizeof(mina));
	queue<int> q;
	dis[s]=0;
	q.push(s);
	vis[s]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=0;i<ve[x].size();i++)
		{
			table y=ve[x][i];
			if(dis[y.to]>dis[x]+y.val&&f[y.id]>0)
			{
				dis[y.to]=dis[x]+y.val;
				where[y.to]=y.id;
				from[y.to]=x;
				mina[y.to]=min(f[y.id],mina[x]);
				if(!vis[y.to])
				{
					q.push(y.to);
					vis[y.to]=1;
				}
			}
		}
	}
	return dis[t]!=1061109567;
}
int zeng()
{
	for(int i=t;i!=s;i=from[i])
	{
		f[where[i]]-=mina[t];
		f[where[i]^1]+=mina[t];
	}
	return mina[t]*dis[t];
}
int dinic()
{
	int ans=0;
	while(spfa())
	{
		ans+=zeng();
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	s=0,t=n*2+1;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		ve[s].push_back((table){i,tot,x}),f[tot++]=1;
		ve[i].push_back((table){s,tot,-x}),f[tot++]=0;
		ve[s].push_back((table){i+n,tot,0}),f[tot++]=1;
		ve[i+n].push_back((table){s,tot,0}),f[tot++]=0;
		ve[i].push_back((table){t,tot,0}),f[tot++]=1;
		ve[t].push_back((table){i,tot,0}),f[tot++]=0;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		int a=min(x,y),b=max(x,y);
		ve[a+n].push_back((table){b,tot,z}),f[tot++]=1;
		ve[b].push_back((table){a+n,tot,-z}),f[tot++]=0;
	}
	printf("%d\n",dinic());
	return 0;
}