题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2121
题意是有n个点(0--n-1),m条有向边,问以那个点作为起点使得最小生成树的权值最小,如果可以构成输出权值和顶点编号,否则输出impossible。
对于这种不定根的题,在不知道虚根这个东西前我是暴力去写的,就是以每一个点都为顶点跑一遍朱刘算法求最小值,按理说因该是TLE才对,然后被我写WA了....然后来说一下用虚根的写法,很巧妙...对于已经建好的图的基础上再额外的加一个点,让这个点与其他的n个点都连一条边,边的权值为前n个点的权值之和再+1,所以现在是有n+1个点,m+n条边。
例如题中的第二个样例,以新加的这个4这个点为根,会得到如下图的图。
然后我们以编号为4的点为根,跑朱刘算法,用橙色线标记出来的就是一个最小生成树,所以最后的生成树的权值就是ans-sum(sum是前m条边的权值之和+1)。对于找最小根的情况,我们需要在寻找最小弧的时候判断一下就好了,因为存的边是先存的前m条边,再存的后n条边,所以对于前m条边都进行完入边操作后就剩下0这个结点还没有入边,所以在后n条边中更新了0这个点的入边,而且此时0点的最小入边的权值就是71,所以就可以判断出0就是我们要找的最小根了,所以标记一下当前的边的编号,然后减去m即为所求。如果最后跑出来的结果是大于等于2*sum,就说明权值为71的边选了两条,所以不能构成最小生成树,这种情况判断一下就好了。虚根的写法不难理解,结合代码想一下就好了。
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 10005;
struct Edge{
int u, v, cost;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN];
int n,m,root,pos,num;
void add(int u,int v,int w){
edge[num].u = u;
edge[num].v = v;
edge[num++].cost = w;
}
int solve()
{
int res = 0;
while (1){
for(int i=0;i<n;i++) in[i] = INF;
for(int i=0;i<num;++i){
int u = edge[i].u, v = edge[i].v;
if(edge[i].cost < in[v] && u != v){
pre[v] = u;
in[v] = edge[i].cost;
if(u == root) pos = i; // 标记最小根
}
}
for (int i = 0; i < n; i++){
if (i != root && in[i] == INF) return -1;
}
int tn = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for(int i = 0; i < n; i++){
res += in[i];
int v = i;
while(vis[v] != i && id[v] == -1 && v != root){
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1){
for(int u = pre[v]; u != v ; u = pre[u]) id[u] = tn;
id[v] = tn++;
}
}
if (tn == 0) break;
for (int i = 0; i < n; i++){
if(id[i] == -1) id[i] = tn++;
}
for (int i = 0; i < num; i++){
int v = edge[i].v;
edge[i].u = id[edge[i].u];
edge[i].v = id[edge[i].v];
if (edge[i].u != edge[i].v) edge[i].cost -= in[v];
}
n = tn;
root = id[root];
}
return res;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
int sum = 0;
num = 0;
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
sum += w;
add(u, v, w);
}
sum ++;
for(int i=0;i<n;i++){
add(n, i, sum);
}
n ++;
root = n - 1;
int ans = solve();
if(ans == -1 || ans >= 2 * sum){
puts("impossible");
}
else printf("%d %d\n", ans - sum, pos - m);
puts("");
}
return 0;
}