Teen Girl Squad
Input: Standard Input
Output: Standard Output
You are part of a group of n teenage girls armed with cellphones. You have some news you want to tell everyone in the group. The problem is that no two of you are in the same room, and you must communicate using only cellphones. What's worse
is that due to excessive usage, your parents have refused to pay your cellphone bills, so you must distribute the news by calling each other in the cheapest possible way. You will call several of your friends, they will call some of their friends, and so on
until everyone in the group hears the news.
Each of you is using a different phone service provider, and you know the price of girl A calling girl B for all possible A and B. Not all of your friends like each other, and some of them will never call people they don't like. Your job is to find the cheapest
possible sequence of calls so that the news spreads from you to all n-1 other members of the group.
Input
The first line of input gives the number of cases, N (N<150). N test cases follow. Each one starts with two lines containing n
40,000)
girl v costs w cents
Output
For each test case, output one line containing "Case #x:" followed by the cost of the cheapest method of distributing the news. If there is no solution, print "Possums!" instead.
Sample Input Sample Output
4
2
1
0 1 10
2
1
1 0 10
4
4
0 1 10
0 2 10
1 3 20
2 3 30
4
4
0 1 10
1 2 20
2 0 30
2 3 100
|
Case #1: 10
Case #2: Possums!
Case #3: 40
Case #4: 130
|
最小树形图
有向图的最小生成树，并且规定了起点。
解法：1.首先dfs判断一下起点可达其他任意点，否则不存在树形图。
2.为每个点找一条最小的入边，如果没环那么这些边就构成了最小树形图，转入4；否则转入3.
3.将环上每条边的边权加入到ans中，同时形成新的点new，对于环内多有的点i，如果存在边<j,i>则<j，new>的边权等于所有 <j,i>-<pre[i],i>中最小的（因为缩点后再次构图必须从环中去除一条边<pre[i],i>再添加一条最小边<x,i>，这样就可以保证答案的正确性，很巧妙，换个图就很清晰了）,<new,j>的边权=所有<i,j>的最小值，缩点完成，转向2.
4.缩点后n个点，n-1条边，切无环，此时就是一颗连通树了，ans+=这n-1条边的边权记得答案；
以上是国人发明的“朱刘算法”，邻接矩阵复杂度（n ^3）临界表复杂度（VE）。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#define for0(a,b) for(a=0;a<b;++a)
#define for1(a,b) for(a=1;a<=b;++a)
#define foru(i,a,b) for(i=a;i<=b;++i)
#define ford(i,a,b) for(i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;
const int maxm = 40000 + 5;
const int INF = 1e9;
struct Edge{ int u, v, cost;};
Edge edge[maxm];
int pre[maxn], id[maxn], vis[maxn], in[maxn];
int zhuliu(int root, int n, int m, Edge edge[])
{
int res = 0, u, v;
int i, j;
while(1){
for0(i,n) in[i] = INF;
for0(i,m) if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v]){
pre[edge[i].v] = edge[i].u;
in[edge[i].v] = edge[i].cost;
}
for0(i,n) if(i != root && in[i] == INF) return -1;//不能存在最小树形图
int tn = 0;
memset(id, -1, sizeof id );
memset(vis, -1, sizeof vis );
in[root] = 0;
for0(i,n)
{
res += in[i];
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; //没有有向环
for0(i,n) if(id[i] == -1)
id[i] = tn++;
for(i=0; i<m; )
{
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];
else
swap(edge[i], edge[--m]);
}
n = tn;
root = id[root];
}
return res;
}
int g[maxn][maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.cpp","r",stdin);
freopen("out.cpp", "w", stdout);
#endif // ONLINE_JUDGE
int n, m;
int T, i, j;
scanf("%d", &T);
for(int cas=1; cas<=T; ++cas)
{
scanf("%d%d", &n, &m);
for0(i,n) for0(j,n)
g[i][j] = INF;
int u, v, c;
while(m--)
{
scanf("%d%d%d", &u, &v, &c);
if(u==v) continue;
g[u][v] = min(g[u][v], c);
}
int e = 0;
for0(i,n) for0(j,n) if(g[i][j]<INF){
edge[e].u = i;
edge[e].v = j;
edge[e++].cost = g[i][j];
}
int ans = zhuliu(0, n, e, edge );
printf("Case #%d: ", cas);
if(ans == -1) printf("Possums!\n");
else printf("%d\n", ans);
}
return 0;
}