题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2124
题意就是一个人xxx要给n-1个人打电话,但是有些人有其他人的联系方式,有些人没有,问xxx想要传达一条信息,能否让其余的n-1个人收到,能的话输出最小花费。
就是一个有向图的最小生成树,用朱刘算法模板就好了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 40005;
struct Edge{
int u, v, cost;
}edge[MAXM];
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN];
int T,n,m,root;
int solve()
{
int res = 0;
while (1){
for(int i=0;i<n;i++) in[i] = INF;
for(int i=0;i<m;++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;
}
}
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 < m; 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()
{
int Case = 1;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);
}
root = 0;
int ans = solve();
printf("Case #%d: ",Case ++);
if(ans == -1) printf("Possums!\n");
else printf("%d\n", ans);
}
return 0;
}