首页 > 代码库 > ACdream 1083 有向无环图dp
ACdream 1083 有向无环图dp
题目链接:点击打开链接
人民城管爱人民
Problem Description
一天GG正在和他的后宫之一的MM在外面溜达,MM突然说了一句,“我想吃鸡蛋灌饼”……当他们吃的正high的时候,城管出现了!作为传说中的最强军事力量,卖鸡蛋灌饼的小贩在他们面前也只算是战力为的5的渣滓,一秒钟就被秒杀了……
在这场屠杀中,GG和他的后宫本来只是围观群众,但是不幸的是,城管看到了GG胃里的鸡蛋灌饼,他们要逮捕GG!但是GG显然不能让他们如愿,于是GG带着后宫开始了往大运村的逃亡之旅。
整个地图有n个路口,灌饼摊在0号路口,大运村在n-1号路口。有m条只能单向通过的道路连接这n个路口,每条道路用一个正整数表示走过需要的时间。整个地图没有环路,但两个路口之间可能有多条通路。现在GG希望以最短的时间到大运村,但不幸的是,城管为了抓住他动用了卫星对他进行空中跟踪,并且会在某一时刻空降到某一条道路上进行封锁(封锁会在瞬间完成,可惜动静太大了GG也能在第一时间知道哪条道路被封锁了),之后这条路就无法通过了。在整个行动中只会出现一次空降,而且不会在GG经过这条道路的时候进行封锁,也就是说,不会在GG在某条路上走了一半的时候封锁这条路。而且,城管们希望尽可能的延缓GG到达大运村的时间。
现在GG希望知道,自己多久能到达大运村,方便安排之后和其他后宫的约会。
注意双方是以博弈的思想来进行选择,即GG希望时间最短,城管希望时间最长,而且他们都非常聪明会做出最佳的选择。
Input
输入第一行为数据组数T(T<=30)。
每组数据第一行包含两个整数n,m(2<=n<=10000,1<=m<=100000),表示路口数和道路数。之后m行描述了所有的道路,每行有三个整数u,v,w(0<=u,v<n,0<w<=1000),表示路口u到路口v有一条需要w时间走过的道路。
Output
Sample Input
2 5 6 0 1 1 1 2 1 2 4 1 1 4 3 0 3 2 3 4 1 3 4 0 1 1 0 1 2 1 2 3 1 2 4
Sample Output
4 5
Source
思路:
1、首先这个dp一定是逆向拓扑序(把所有边反向进行拓扑排序),这样我们在计算u点时,通过有向边(u->v)把u点的状态从v点转移过来,能保证v点一定是已计算过的
2、用dis[i]表示i点到终点的最短路,dp[i]表示i点到终点的删边最短路(这里所谓的删边,删除的边是在i-终点的路径上)
3、那么我们设GG站在u点,通过u->v的边把状态从v转移过来。
4、计算dis[u]比较容易,就是min(dis[v]+edge[i].dis)
5、计算dp[u]:根据定义dp[u] 是删边最短路,则删除的边是在u-终点的路径上,那么显然有2种情况
1)删除u-v这种与u相连的边
2)删除v-终点上的边
对于2):那么GG有主动权,显然是选择edge[i].dis + dp[v] 中最小的(我们设这个最小值为smin)
对于1):军队拥有主动权,军队一定选择删掉一条边,那么删完以后GG自然还是选择走最短路,也就是GG只能选择edge[i].dis+dis[v] 中次小值(设这个值为dmin
这里注意的是,军队拥有的主动权是可以任意选择一条边,所以dp[u]=max(dmin, smin)
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<set> #include<queue> #include<math.h> #include<map> using namespace std; #define N 10050 #define M 100500 #define inf 10000000 struct Edge{ int from, to, dis, nex; }edge[M<<1]; int head[N], edgenum; void add(int u, int v, int d){ Edge E={u,v,d,head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int n,m; int sp[N], in[N]; void topsort(){//把图进行拓扑序 queue<int>q; for(int i = 0; i < n; i++)if(in[i]==0)q.push(i); int top = 0; while(!q.empty()){ int u = q.front(); q.pop(); sp[top++] = u; for(int i = head[u]; ~i; i = edge[i].nex)if(i&1){ int v = edge[i].to; in[v]--; if(!in[v])q.push(v); } } } int dp[N][2], a[M];//dp[u][0]表示1到u的最短路 dp[u][1]表示1到u的次小最短路 void work(int u){ if(u == n-1){ dp[u][0] = dp[u][1] = 0; return ; } int top = 0, smin = inf; for(int i = head[u]; ~i; i = edge[i].nex)if(!(i&1)){ int v = edge[i].to; dp[u][0] = min(dp[u][0], dp[v][0]+edge[i].dis); smin = min(smin, dp[v][1]+edge[i].dis); a[top++] = dp[v][0] + edge[i].dis; } if(top<2){dp[u][1] = inf; return ;} int fir = a[0], sec = a[1]; if(fir>sec)swap(fir,sec); for(int i = 2; i < top; i++){ if(a[i]<=fir) sec = fir, fir = a[i]; else sec = min(sec, a[i]); } dp[u][1] = max(smin, sec); } void init(){memset(head, -1, sizeof head);edgenum = 0;} int main(){ int T, i, j, u, v, d;scanf("%d",&T); while(T--){ init(); memset(in, 0, sizeof in); scanf("%d %d",&n,&m); while(m--){ scanf("%d %d %d",&u,&v,&d); add(u,v,d); add(v,u,d); in[u]++; } topsort(); for(i = 0; i < n; i++) dp[i][0] = dp[i][1] = inf; for(i = 0; i < n; i++) work(sp[i]); if(dp[0][1]==inf)dp[0][1] = -1; printf("%d\n",dp[0][1]); } return 0; }