UVA--10462

解题思路:三种输出情况,很简单,但用prim()写就WA到底,感觉所有情况都考虑了啊,可能是定点不一定是1到N,所以会出现bug.所以建议还是用kruskal写简单一些,别怕超时,大胆写.

kruskal代码如下:

#include 
#include 
#include 
using namespace std;const int N = 110;
const int M = 220;
const int INF = 1000000000;
int n, m, T, ans1, ans2, ise[N], f[N];
struct edge {int u, v, cost;
}e[M];bool cmp( edge a, edge b ) {return a.cost < b.cost;
}
int find ( int x ) {return f[x] == x ? x: f[x] = find(f[x]);
}
int Kru() {int ans = 0, num = 0, id = 0;for ( int i = 1; i <= n; ++i ) f[i] = i;for ( int i = 0; i < m; ++i ) {int x = e[i].u;int y = e[i].v;int a = find(x);int b = find(y);if ( a != b ) ise[id++] = i, f[a] = b, ans += e[i].cost;}for ( int i = 1; i <= n; ++i ) if ( i == find(i) ) num++;if ( num > 1 ) return INF;else return ans;
}
int Kru_1( int del ) {int ans = 0, num = 0;for ( int i = 1; i <= n; ++i ) f[i] = i;for ( int i = 0; i < m; ++i ) {if ( i == del ) continue;int x = e[i].u;int y = e[i].v;int a = find(x);int b = find(y);if ( a != b ) f[a] = b, ans += e[i].cost;}for ( int i = 1; i <= n; ++i ) if ( i == find(i) ) num++;if ( num > 1 ) return INF;else return ans;
}
int main()
{int idx = 1;scanf("%d", &T);while ( T-- ) {scanf("%d%d", &n, &m);for ( int i = 0; i < m; ++i ) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].cost);sort( e, e+m, cmp );ans1 = Kru(), ans2 = INF;printf("Case #%d : ", idx++);if ( ans1 == INF ) {printf("No way\n");continue;}for ( int i = 0; i < n-1; ++i ) {int x = ise[i];ans2 = min( ans2, Kru_1(x) );}if ( ans2 == INF ) printf("No second way\n");else printf("%d\n", ans2);}return 0;
}

另外附上我WA的prim():

#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
struct stu{int x,y,c;
};
stu num[210];
int n,m;
int map[110][110];
int inMST[110][110];
int MST[110][110];
int vis[110];
int per[110];
int low[110];
int see[110][110];
void inin(){for(int i=1;i<=n;i++){map[i][i]=0;for(int j=1;jc){map[a][b]=map[b][a]=c;}}
}
int slove(){int temp,v,i,j,k,fa,sum,w,x,y;v=0;sum=INF;memset(vis,0,sizeof(vis));memset(inMST,0,sizeof(inMST));memset(MST,0,sizeof(MST));for(i=1;i<=n;i++){low[i]=map[1][i];per[i]=1;}per[1]=0;vis[1]=1;for(i=2;i<=n;i++){temp=INF;for(j=1;j<=n;j++){if(!vis[j]&&low[j]map[k][j]){low[j]=map[k][j];per[j]=k;}}}for(i=1;i<=m;i++){x=num[i].x;y=num[i].y;w=INF;if(!inMST[x][y])w=v-MST[x][y]+num[i].c;else if(see[x][y]>1)w=v-map[x][y]+num[i].c;if(w

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！