bzoj 4669 抢夺

Posted on | Views:

二分答案 + 费用流.

  • 答案显然可以二分,只需要如何验证一个答案 $mid$ 是否合法.
  • 考虑第一波同时出发的人,他们会选择最优的路径,而后来的人选择的路径必定与他们相同.
  • 于是可以通过增广计算出在 $mid$ 天内到达的人数.而退流操作对应的贡献也是正确的,所以不需要另外考虑.
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e4+10;
const int inf=1e9;
int ecnt=-1,head[MAXN];
struct edge
{
	int nx,to,flow,dis;
}E[MAXN];
void addedge(int u,int v,int flow,int dis)
{
	++ecnt;
	E[ecnt].nx=head[u];
	E[ecnt].to=v;
	E[ecnt].flow=flow;
	E[ecnt].dis=dis;
	head[u]=ecnt;
}
void ins(int u,int v,int flow,int dis)
{
	addedge(u,v,flow,dis);
	addedge(v,u,0,-dis);
}
int n,m,k;
int dis[MAXN],flow[MAXN],pre[MAXN],lst[MAXN],vis[MAXN];
queue<int> q;
bool spfa(int S,int T)
{
	while(!q.empty())
		q.pop();
	for(int i=1;i<=n;++i)
	{
		vis[i]=0;
		flow[i]=inf;
		dis[i]=inf;
	}
	pre[T]=-1;
	vis[S]=1;
	dis[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=E[i].nx)
		{
			int v=E[i].to;
			if(E[i].flow>0 && dis[v]>dis[u]+E[i].dis)
			{
				dis[v]=dis[u]+E[i].dis;
				flow[v]=min(flow[u],E[i].flow);
				pre[v]=u;
				lst[v]=i;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return pre[T]!=-1;
}
int Dist[MAXN],Flow[MAXN],tot=0;
int mcmf(int S,int T)
{
	while(spfa(S,T))
	{
		int now=T;
		while(now!=S)
		{
			E[lst[now]].flow-=flow[T];
			E[lst[now]^1].flow+=flow[T];
			now=pre[now];
		}
		++tot;
		Dist[tot]=dis[T];
		Flow[tot]=flow[T];
	}
}
void init()
{
	memset(head,-1,sizeof head);
	ecnt=-1;
	tot=0;
}
bool check(int mid)
{
	ll tmp=k;
	for(int i=1;i<=tot && tmp>0;++i)
		tmp-=1LL*(mid-Dist[i]+1)*Flow[i];
	return tmp<=0;
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		init();
		for(int i=1;i<=m;++i)
		{
			int u=read()+1,v=read()+1,c=read();
			ins(u,v,c,1);
		}
		mcmf(1,n);
		int ans=-1,L=0,R=n+k+1;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(check(mid))
				ans=mid,R=mid-1;
			else
				L=mid+1;
		}
		if(ans==-1)
			puts("No solution");
		else
			printf("%d\n",ans);
	}
	return 0;
}