ural 1416. Confidential (次小生成树模板题)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月11日 星期一 20时44分28秒
  4File Name :code/ural/1416.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <string>
 15#include <cmath>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26using namespace std;
 27const double eps = 1E-8;
 28const int dx4[4]={1,0,0,-1};
 29const int dy4[4]={0,-1,1,0};
 30const int inf = 0x3f3f3f3f;
 31const int N=505;
 32int n,m;
 33int f[N];
 34int mst;
 35int ans;
 36int cnt = 0 ;
 37vector < pi > e[N*N];
 38bool flag;
 39struct Edge
 40{
 41    int u,v;
 42    int w;
 43    int in;//标记边是否在生成树中。
 44    bool operator < (Edge b)const
 45    {
 46	return w<b.w;
 47    }
 48    void input()
 49    {
 50	scanf("%d%d%d",&u,&v,&w);
 51    }
 52}E[N*N];
 53void init()
 54{
 55    for ( int i = 1 ; i <= n ; i++) f[i] = i;
 56    for ( int i = 1 ; i <= n ; i++) e[i].clear();
 57}
 58int root ( int x)
 59{
 60  //  cout<<"x:"<<x<<" f[x]:"<<f[x]<<endl;
 61    if (x!=f[x]) f[x] = root (f[x]);
 62    return f[x];
 63}
 64void merge( int x,int y)
 65{
 66    int rx = root (x);
 67    int ry = root (y);
 68    if (rx==ry) return ;
 69    f[rx] = ry; 
 70  //  if (rx<ry) f[ry] = rx;
 71  //  else f[rx]=ry;
 72}
 73void kruskal(int k)
 74{
 75    for ( int i = 1 ; i <= n ; i++) f[i] = i ;
 76    mst = 0 ;
 77    cnt =  0;
 78    for ( int i = 1; i <= m ; i++)
 79    {
 80	int u = E[i].u;
 81	int v = E[i].v;
 82	int w = E[i].w;
 83	if (i==k) continue;
 84	if (root(u)==root(v)) continue;
 85	merge(u,v);
 86	cnt++;
 87	mst+=w;
 88	if (cnt>=n-1) break;
 89    }
 90    if (cnt<n-1) return ;
 91    ans = min(ans,mst);
 92}
 93int main()
 94{
 95	#ifndef  ONLINE_JUDGE 
 96	freopen("code/in.txt","r",stdin);
 97  #endif
 98	cin>>n>>m;
 99	init();
100	for ( int i = 1 ; i <= m ; i++)
101	{
102	    E[i].input();
103	    int u = E[i].u;
104	    int v = E[i].v;
105	    int w = E[i].w;

 1	    e[u].push_back(make_pair(v,w));
 2	    e[v].push_back(make_pair(u,w));
 3	}
 4	sort(E+1,E+m+1);
 5	mst = 0 ;
 6	cnt = 0 ;
 7	for ( int i = 1 ; i <= m ; i++)
 8	{
 9	    int u = E[i].u;
10	    int v = E[i].v;
11	    int w = E[i].w;
12	    if (root(u)==root(v)) continue;
13	    E[i].in = 1;
14	    merge(u,v);
15	    cnt++;
16	    mst+=w;
17	}
18	if (cnt<n-1)
19	{
20	    puts("Cost: -1");
21	    puts("Cost: -1");
22	    return 0;
23	}
24	printf("Cost: %d\n",mst);
25	ans = inf;
26	for ( int i = 1 ; i <= m ; i++)
27	{
28	    if (E[i].in==0) continue;
29	   // cout<<"hhh?"<<endl; 
30	    kruskal(i);
31	}
32	if (ans==inf) ans = -1;
33	printf("Cost: %d\n",ans);
34  #ifndef ONLINE_JUDGE  
35  fclose(stdin);
36  #endif
37    return 0;
38}