BZOJ 1922 大陆争霸

发表于 | 更新于

Link

毫无头绪。。 保护着N的必须摧毁，挡着N的可以选择一个摧毁？ 有保护关系的必须摧毁，挡着的可以选择一个摧毁？ 处理出摧毁某个点的最短时间？？取max？ 各个点的摧毁是互不影响的？？ 先把环去掉？？

Solution

性质

限制一个点pp的最早到达时间tt的有

  1. 经过图上的点，消灭掉沿途的各种阻挡它的，然后到达它的时间;
  2. 保护它的所有点集SS中,max(tu∣u∈S)max(t_u|u \in S)

    方法

    对这两个量跑Dijstra。每次更新要更新相邻点的最早到达时间，和被保护点的最早不被保护的时间。 每次循环，选择一个没有被保护，且真实时间 到 达 时 间 ， 不 被 保 护 时 间 最小的点来进行松弛。

以下内容纯属一个蒟蒻的自言自语！！求打脸！！

Dijstra算法正确性

设用过的点集为SS，则需要证明每次选出V−SV-S中distudist_u最小的那个点uu的distu==spudist_u==sp_u。 假设 ，那spusp_u的路径一定是从ss走到SS中的一个点xx，从xx走到V−SV-S中的点yy，再从yy走到uu。 则一定有spy==distysp_y==dist_y。

假如说 ，distydist_y还可以被w(w∈V−S)w(w\in V-S)松弛，那到uu的最短路就是从s→p(p∈S)→w(w∈V−S)→y→us\rightarrow p(p \in S)\rightarrow w(w\in V-S)\rightarrow y\rightarrow u，到uu的最短路就不会来源于yy而是来源于ww了。

而spy≥distusp_y\ge dist_u 又要spy+D(y,u)<distusp_y+D(y,u)< dist_u 这是不可能的。所以distu==spudist_u==sp_u。

对于这道题

假设SS中的点的答案已经最优，且V−SV-S中的点pp能优化新选出的uu。那么pp没被加入SS一定是因为受到了限制。而限制它的那个点的值都≥max(dist[u],limit[u])\ge max(dist[u],limit[u])，所以pp不可能去优化uu。

总结

Dijstra解决的问题可以明确地划分出阶段来，采用Dijstra的变形必须要满足每次迭代选出的点的答案已经最优。这虽然限制它的灵活性，但有时候也是优势。对于这个题目，因为涉及到最小值中取最大，就必须保证用来更新一个点的最小值的确是最小的，否则如果变小之后，更新也没有意义了。 相反，SPFA在转移的时候不需要保证当前最优，可以用队列来反反复复地修改松弛，所以更加灵活，但就解决不了这种鬼畜的问题了。 关于SPFA的转移作用，参见TA爷的神文 OK。。 不得不说这是一道好题。。

Tips

这类鬼畜的最优化问题怎么想到正解？ 寻找限制最优解的量，根据其特点转化成DP/最大流/最小割/最短路之类的。建模能力还在分析问题的能力之后。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
const int MAXN=3000+10,MAXM=70000+10;
const LL INF=LLONG_MAX;
using std::max;
using std::pair;
using std::vector;
using std::greater;
using std::priority_queue;
//SPFA在转移的时候不需要保证当前最优，所以如果当前点不是最优的答案会影响到结果，就不能用SPFA
//相反,DIJSTRA在转移的时候当前点已经是最优的了，所以。
int proc[MAXN],edge[MAXN][MAXN],n;bool prot[MAXN][MAXN];
LL SP(int s,int t)
{
	static LL dist[MAXN],limit[MAXN];
	static bool ud[MAXN];	
	memset(dist,31,sizeof(dist));
	limit[s]=dist[s]=0;
	for(int i=1;i<=n;i++)//n-1
	{
		LL rv=INF;int cur;
		for(int u=1;u<=n;u++)
			if(!ud[u] && !proc[u] && chkmn(rv,max(dist[u],limit[u])))
				cur=u;	
		for(int u=1;u<=n;u++)
		{
			if(prot[cur][u])
			{
				proc[u]--;
				chkmx(limit[u],rv);
			}
			chkmn(dist[u],rv+edge[cur][u]);
		}
		ud[cur]=1;
	}
	return max(dist[t],limit[t]);
}
int main()
{
	freopen("input","r",stdin);
	int m;get(n),get(m);
	memset(edge,31,sizeof(edge));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;get(u),get(v),get(w);
		chkmn(edge[u][v],w);
	}
	for(int i=1;i<=n;i++)
	{
		int x;get(proc[i]);
		for(int j=1;j<=proc[i];j++) 
			get(x),prot[x][i]=1;
	}
	printf("%lld\n",SP(1,n));
	return 0;
}
/* AC Record(Bugs) *
 *
 * * * * * * * * * */