最小树形图,测模版….
2248.Channel DesignTime Limit:1.0 Seconds Memory Limit:65536KTotal Runs:2199 Accepted Runs:740
We need irrigate our farms, but there is only one source of water nearby. So we need build some water channels with minimum cost.
In Figure (a),V1indicates the source of water. OtherN-1 nodes in the Figure indicate the farms we need to irrigate. An edge represents you can build a channel between the two nodes, to irrigate the target. The integers indicate the cost of a channel between two nodes.
Figure (b) represents a design of channels with minimum cost.
Input
There are multiple cases, the first line of each case contains two integersNandM(2 ≤N≤ 100; 1 ≤M≤ 10000),Nshows the number of nodes. The followingMlines, each line contains three integersijcij, means we can build a channel from nodeVito nodeVj, which costcij. (1 ≤i,j≤N;i≠j; 1 ≤cij≤ 100)
The source of water is alwaysV1.The input is terminated byN=M= 0.
Output
For each case, output a single line contains an integer represents the minimum cost.
If no design can irrigate all the farms, output "impossible" instead.
Sample Input5 81 2 31 3 52 4 23 1 53 2 53 4 43 5 75 4 33 31 2 31 3 53 2 10 0Sample Output176
Problem setter:Hill
Source:TJU Contest August 2006Submit List Runs Forum Statistics
/* ***********************************************Author:CKbossCreated Time :2015年07月04日 星期六 23时35分05秒File Name:TJU2248.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=110;int n,m;struct Edge{int u,v,cost;};Edge edge[maxn*maxn];int pre[maxn],id[maxn],vis[maxn],in[maxn];int zhuliu(int root,int n,int m,Edge edge[]){int res=0,u,v;while(true){for(int i=0;i<n;i++) in[i]=INF;for(int i=0;i<m;i++){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;}}for(int i=0;i<n;i++)if(i!=root&&in[i]==INF) return -1;int tn=0;memset(id,-1,sizeof(id));memset(vis,-1,sizeof(vis));in[root]=0;for(int i=0;i<n;i++){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;for(int i=0;i<n;i++)if(id[i]==-1) id[i]=tn++;for(int 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];elseswap(edge[i],edge[–m]);}n=tn;root=id[root];}return res;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w); u–; v–;edge[i].u=u; edge[i].v=v; edge[i].cost=w;}int ans=zhuliu(0,n,m,edge);if(ans==-1) puts("impossible");else printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，不要轻言放弃，否则对不起自己
