MYF

UVa 11183 Teen Girl Squad

Posted on | In | | Visitors

题目链接

UVa 11183

方法：最小树形图

题目分析

题目大意

n个点，m条边，已知每两个人之间的联系关系以及联系花费，问如何采用最小的花费联系到所有人，从下标为0号的人开始

解析

直接上板子就行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#define debug3(x,y,z) cout<<"Debug : ---"<<x<<" , "<<y<<" , "<<z<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;

typedef int mytype;
const int Vmax=1005;
const int Emax=40005;
struct edge//有向边
{
    int u,v;    //起点 终点
    mytype l;   //权值
} e[Emax];
int pre[Vmax],ID[Vmax],vis[Vmax];
mytype In[Vmax];
void init(int m)
{
    for(int i=1; i<=m; i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].l);
        e[i].u ++ ,e[i].v++;
    }
}
mytype Directed_MST(int root,int NV,int NE)
{
    //    memset(pre,0,sizeof(pre));
    mytype ret = 0;
    while(1)
    {
        //1.找最小入边
        for(int i=1; i<=NV; i++)
            In[i] = INF;
        for(int i=1; i<=NE; i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            if(e[i].l < In[v] && u != v)
            {
                pre[v] = u;
                In[v] = e[i].l;
            }
        }
        for(int i=1; i<=NV; i++)
        {
            if(i == root)
                continue;
            if(fabs(In[i]-INF)<eps)
                return -1;//除了跟以外有点没有入边,则根无法到达它
        }
        //2.找环
        int cntnode = 0;
        memset(ID,-1,sizeof(ID));
        memset(vis,-1,sizeof(vis));
        In[root] = 0;
        for(int i=1; i<=NV; i++) //标记每个环
        {
            ret += 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)
            {
                ID[v] = ++cntnode;
                for(int u = pre[v] ; u != v ; u = pre[u])
                    ID[u] = cntnode;
            }
        }
        if(cntnode == 0)
            break;//无环
        for(int i=1; i<=NV; i++)
            if(ID[i] == -1)
                ID[i] = ++cntnode;
        //3.缩点,重新标记
        for(int i=1; i<=NE; i++)
        {
            int v = e[i].v;
            e[i].u = ID[e[i].u];
            e[i].v = ID[e[i].v];
            if(e[i].u != e[i].v)
            {
                e[i].l -= In[v];
            }
        }
        NV = cntnode;
        root = ID[root];
    }
    return ret;
}
bool judge(mytype ans)  //判断能否成树
{
    return fabs(ans+1)>eps;
}
int main(){
    int T,n,m,cas=1;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        init(m);
        int ans = Directed_MST(1, n, m);
        printf("Case #%d: ",cas++);
        if (judge(ans))
            printf("%d\n",ans);
        else
            puts("Possums!");
    }
}