2015多校第8场HDU5385贪心，最小生成树

题目链接&＃xff1a;http://acm.hdu.edu.cn/showproblem.php?pid&＃61;5385

题意&＃xff1a;给了一个有向连通图&＃xff0c;要给图中的每一条边加一个权值&＃xff0c;使得满足dis[1]dis[x&＃43;1]>dis[n]成立&＃xff0c;x可以取到n。

解法&＃xff1a;官方题解

如果我们知道每个点的dis值和最短路径树的话&＃xff0c;方案是很容易构造的

我们可以采取贪心做法&＃xff0c;一开始将1号点作为最短路径树的根&＃xff0c;然后左边从2开始&＃xff0c;右边从n开始&＃xff0c;只要之前加入的点有边连向他们就加入

这样一个点加入的时间就是他的dis值&＃xff0c;最短路径树上的父亲也可以确定&＃xff0c;于是输出时非树边长度为n&＃xff0c;树边长度为两个端点dis之差

#include
using namespace std;
const int maxn &＃61; 1e5&＃43;10;
int head[maxn], edgecnt;
void init(){edgecnt&＃61;0;memset(head,-1,sizeof(head));
}
struct edge{int to,next;
}E[maxn];
void add(int u, int v){E[edgecnt].to &＃61; v, E[edgecnt].next &＃61; head[u], head[u] &＃61; edgecnt&＃43;&＃43;;
}
struct node{int u,v;
}q[maxn];
int T,n,m,dis[maxn],vis[maxn];int main()
{scanf("%d", &T);while(T--){init();memset(vis, 0, sizeof(vis));scanf("%d %d", &n,&m);for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){int u,v;scanf("%d %d", &u,&v);q[i].u &＃61; u, q[i].v &＃61; v;add(u, v);}vis[1] &＃61; vis[n] &＃61; 1;int l&＃61;1,r&＃61;n,u;for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){if(vis[l]&＃61;&＃61;0) u&＃61;r--;else u&＃61;l&＃43;&＃43;;dis[u] &＃61; i;for(int j&＃61;head[u]; ~j; j&＃61;E[j].next){int v&＃61;E[j].to;vis[v]&＃61;1;}}
// for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){
// printf("%d ", dis[i]);
// }
// printf("\n");for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){if(dis[q[i].u] }