Date Time

16/07/12 03:50

Author

URAL1416
题意：次小生成树模板题

思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

写的时候。。因为点数是500。。我把边集的数组大小开成了500.。。交了10遍越界才意识到问题在哪里。。。真的是智商掉线啊orz…




/* ***********************************************
Author :111qqz
Created Time :2016年07月11日 星期一 20时44分28秒
File Name :code/ural/1416.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=505;
int n,m;
int f[N];
int mst;
int ans;
int cnt = 0 ;
vector < pi > e[N*N];
bool flag;
struct Edge
{
    int u,v;
    int w;
    int in;//标记边是否在生成树中。
    bool operator < (Edge b)const
    {
	return w<b.w;
    }
    void input()
    {
	scanf("%d%d%d",&u,&v,&w);
    }
}E[N*N];
void init()
{
    for ( int i = 1 ; i <= n ; i++) f[i] = i;
    for ( int i = 1 ; i <= n ; i++) e[i].clear();
}
int root ( int x)
{
  //  cout<<"x:"<<x<<" f[x]:"<<f[x]<<endl;
    if (x!=f[x]) f[x] = root (f[x]);
    return f[x];
}
void merge( int x,int y)
{
    int rx = root (x);
    int ry = root (y);
    if (rx==ry) return ;
    f[rx] = ry; 
  //  if (rx<ry) f[ry] = rx;
  //  else f[rx]=ry;
}
void kruskal(int k)
{
    for ( int i = 1 ; i <= n ; i++) f[i] = i ;
    mst = 0 ;
    cnt =  0;
    for ( int i = 1; i <= m ; i++)
    {
	int u = E[i].u;
	int v = E[i].v;
	int w = E[i].w;
	if (i==k) continue;
	if (root(u)==root(v)) continue;
	merge(u,v);
	cnt++;
	mst+=w;
	if (cnt>=n-1) break;
    }
    if (cnt<n-1) return ;
    ans = min(ans,mst);
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	cin>>n>>m;
	init();
	for ( int i = 1 ; i <= m ; i++)
	{
	    E[i].input();
	    int u = E[i].u;
	    int v = E[i].v;
	    int w = E[i].w;

	    e[u].push_back(make_pair(v,w));
	    e[v].push_back(make_pair(u,w));
	}
	sort(E+1,E+m+1);
	mst = 0 ;
	cnt = 0 ;
	for ( int i = 1 ; i <= m ; i++)
	{
	    int u = E[i].u;
	    int v = E[i].v;
	    int w = E[i].w;
	    if (root(u)==root(v)) continue;
	    E[i].in = 1;
	    merge(u,v);
	    cnt++;
	    mst+=w;
	}
	if (cnt<n-1)
	{
	    puts("Cost: -1");
	    puts("Cost: -1");
	    return 0;
	}
	printf("Cost: %d\n",mst);
	ans = inf;
	for ( int i = 1 ; i <= m ; i++)
	{
	    if (E[i].in==0) continue;
	   // cout<<"hhh?"<<endl; 
	    kruskal(i);
	}
	if (ans==inf) ans = -1;
	printf("Cost: %d\n",ans);
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

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

139

140

141

142

143

144

145

146

147

148

149

150

151

/* ***********************************************

Author :111qqz

Created Time :2016年07月11日星期一 20时44分28秒

File Name :code/ural/1416.cpp

************************************************ */

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define fst first

#define sec second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ms(a,x) memset(a,x,sizeof(a))

typedef long long LL;

#define pi pair < int ,int >

#define MP make_pair

using namespace std;

const double eps = 1E-8;

const int dx4[4]={1,0,0,-1};

const int dy4[4]={0,-1,1,0};

const int inf = 0x3f3f3f3f;

const int N=505;

int n,m;

int f[N];

int mst;

int ans;

int cnt = 0 ;

vector < pi > e[N*N];

bool flag;

struct Edge

{

int u,v;

int w;

int in;//标记边是否在生成树中。

bool operator < (Edge b)const

{

return w<b.w;

}

void input()

{

scanf("%d%d%d",&u,&v,&w);

}

}E[N*N];

void init()

{

for ( int i = 1 ; i <= n ; i++) f[i] = i;

for ( int i = 1 ; i <= n ; i++) e[i].clear();

}

int root ( int x)

{

// cout<<"x:"<<x<<" f[x]:"<<f[x]<<endl;

if (x!=f[x]) f[x] = root (f[x]);

return f[x];

}

void merge( int x,int y)

{

int rx = root (x);

int ry = root (y);

if (rx==ry) return ;

f[rx] = ry;

// if (rx<ry) f[ry] = rx;

// else f[rx]=ry;

}

void kruskal(int k)

{

for ( int i = 1 ; i <= n ; i++) f[i] = i ;

mst = 0 ;

cnt = 0;

for ( int i = 1; i <= m ; i++)

{

int u = E[i].u;

int v = E[i].v;

int w = E[i].w;

if (i==k) continue;

if (root(u)==root(v)) continue;

merge(u,v);

cnt++;

mst+=w;

if (cnt>=n-1) break;

}

if (cnt<n-1) return ;

ans = min(ans,mst);

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("code/in.txt","r",stdin);

#endif

cin>>n>>m;

init();

for ( int i = 1 ; i <= m ; i++)

{

E[i].input();

int u = E[i].u;

int v = E[i].v;

int w = E[i].w;

e[u].push_back(make_pair(v,w));

e[v].push_back(make_pair(u,w));

}

sort(E+1,E+m+1);

mst = 0 ;

cnt = 0 ;

for ( int i = 1 ; i <= m ; i++)

{

int u = E[i].u;

int v = E[i].v;

int w = E[i].w;

if (root(u)==root(v)) continue;

E[i].in = 1;

merge(u,v);

cnt++;

mst+=w;

}

if (cnt<n-1)

{

puts("Cost: -1");

return 0;

}

printf("Cost: %d\n",mst);

ans = inf;

for ( int i = 1 ; i <= m ; i++)

{

if (E[i].in==0) continue;

// cout<<"hhh?"<<endl;

kruskal(i);

}

if (ans==inf) ans = -1;

printf("Cost: %d\n",ans);

#ifndef ONLINE_JUDGE

fclose(stdin);

#endif

return 0;

}

说点什么

您将是第一位评论人！

111qqz的小窝

老年咸鱼冲锋！

Date Time

Author

Category

Tags

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

说点什么