URAL-1982 Electrification Plan 最小生成树

By | 10月30日
Advertisement

  题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1982

  题意:无向图,给n个点,n^2条边,每条边有个一权值,其中有k个点有发电站,给出这k个点的编号,选择最小权值的边,求使得剩下的点都能接收到电。

  发电站之间显然不能有边,那么把k个点合成一个点,然后在图上就MST就可以了。

  1 //STATUS:C++_AC_31MS_401KB
  2 #include <functional>
  3 #include <algorithm>
  4 #include <iostream>
  5 //#include <ext/rope>
  6 #include <fstream>
  7 #include <sstream>
  8 #include <iomanip>
  9 #include <numeric>
 10 #include <cstring>
 11 #include <cassert>
 12 #include <cstdio>
 13 #include <string>
 14 #include <vector>
 15 #include <bitset>
 16 #include <queue>
 17 #include <stack>
 18 #include <cmath>
 19 #include <ctime>
 20 #include <list>
 21 #include <set>
 22 #include <map>
 23 using namespace std;
 24 //#pragma comment(linker,"/STACK:102400000,102400000")
 25 //using namespace __gnu_cxx;
 26 //define
 27 #define pii pair<int,int>
 28 #define mem(a,b) memset(a,b,sizeof(a))
 29 #define lson l,mid,rt<<1
 30 #define rson mid+1,r,rt<<1|1
 31 #define PI acos(-1.0)
 32 //typedef
 33 typedef __int64 LL;
 34 typedef unsigned __int64 ULL;
 35 //const
 36 const int N=110;
 37 const int INF=0x3f3f3f3f;
 38 const int MOD=95041567,STA=8000010;
 39 const LL LNF=1LL<<60;
 40 const double EPS=1e-8;
 41 const double OO=1e15;
 42 const int dx[4]={-1,0,1,0};
 43 const int dy[4]={0,1,0,-1};
 44 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
 45 //Daily Use ...
 46 inline int sign(double x){return (x>EPS)-(x<-EPS);}
 47 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 48 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 49 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
 50 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 51 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 52 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 53 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 54 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 55 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 56 //End
 57
 58 struct Edge{
 59     int u,v,val;
 60     bool operator < (const Edge& a)const {
 61         return val<a.val;
 62     }
 63 }e[N*N];
 64 int n,k;
 65 int id[N],p[N],w[N][N];
 66
 67 int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
 68
 69 int main()
 70 {
 71  //   freopen("in.txt","r",stdin);
 72     int i,j,a,x,y,ans,cnt;
 73     while(~scanf("%d%d",&n,&k))
 74     {
 75         mem(id,0);
 76         for(i=0;i<k;i++){
 77             scanf("%d",&a);
 78             id[a]=1;
 79         }
 80         k=2;
 81         for(i=1;i<=n;i++){
 82             if(id[i])continue;
 83             id[i]=k++;
 84         }
 85         mem(w,INF);
 86         for(i=1;i<=n;i++){
 87             for(j=1;j<=n;j++){
 88                 scanf("%d",&a);
 89                 w[id[i]][id[j]]=Min(w[id[i]][id[j]],a);
 90             }
 91         }
 92         cnt=0;
 93         for(i=1;i<k;i++){
 94             for(j=i+1;j<k;j++){
 95                 e[cnt].u=i,e[cnt].v=j;
 96                 e[cnt].val=w[i][j];
 97                 cnt++;
 98             }
 99         }
100         sort(e,e+cnt);
101         ans=0;
102         for(i=1;i<k;i++)p[i]=i;
103         for(i=0;i<cnt;i++){
104             x=find(e[i].u);y=find(e[i].v);
105             if(x!=y){
106                 p[y]=x;
107                 ans+=e[i].val;
108             }
109         }
110
111         printf("%d\n",ans);
112     }
113     return 0;
114 }

Similar Posts:

  • Electrification Plan(最小生成树)

    http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=50#problem/D 最小生成树模板,注意的是这里有k个发电站,它们不再需要连接其他的发电站,所以任何两个发电站之间的权值是0: 1 #include<stdio.h> 2 #include<string.h> 3 const int maxn = 110; 4 const int INF = 0x3f3f3f3f; 5 int map[maxn][maxn],

  • UVa 10397 - Connect the Campus (最小生成树)

    链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338 题目: Problem E Connect the Campus Input:standard input Output:standard output Time Limit:2 seconds Many new buildings are un

  • POJ-1861,Network,最小生成树水题,,注意题面输出有问题,不必理会~~

    Network Time Limit: 1000MS Memory Limit: 30000K Special Judge http://poj.org/problem?id=1861 Description Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they ca

  • poj 1789 Truck History 【最小生成树】

    Truck History Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 21592 Accepted: 8393 Description Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. T

  • 最小生成树Prim poj1258 poj2485 poj1789

    poj:1258 Agri-Net Time Limit: 1000 MS Memory Limit: 10000 KB 64-bit integer IO format: %I64d , %I64u Java class name: Main [Submit] [Status] [Discuss] Description Farmer John has been elected mayor of his town! One of his campaign promises was to bri

  • [Sql*Plus] Set up Explain Plan and Autotrace

    之所以把Explain Plan 和 Autotrace的设置放到一起来说,是因为这2者都依赖于同一张表PLAN_TABLE,因此都需要首先创建PLAN_TABLE. 1. Create Table PLAN_TABLE 有时候貌似不需要手动去创建这张表,PLAN_TABLE在数据库安装过程中已经被创建好了.我们可以首先测试下PLAN_TABLE是否已经存在, [email protected]> desc plan_table; Name Null? Type -----------------------

  • (intermediate) 最小生成树 UVA 1504 Genghis Khan the Conqueror

    Genghis Khan( )(1162-1227), also known by his birth name Temujin( ) and temple name Taizu( ), was the founder of the Mongol Empire and the greatest conqueror in Chinese history. After uniting many of the nomadic tribes on the Mongolian steppe, Genghi

  • POJ 1861 &amp;amp;&amp;amp; ZOJ 1542--Network 【最小生成树 &amp;amp;&amp;amp; kruscal &amp;amp;&amp;amp; 水题】

    Network Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cab

  • poj1789Truck History(最小生成树prim算法)

    题目链接: 啊哈哈,点我点我 思路:根据字符串中不同的长度建图,然后求图的最小生成树.. 题目: Truck History Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 18272 Accepted: 7070 Description Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetabl

  • Truck History(最小生成树_prim算法)

    Truck HistoryCrawling in process...Crawling failedTime Limit:2000MS    Memory Limit:65536KB     64bit IO Format:%I64d & %I64u SubmitStatus Practice POJ 1789 Description Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are use

Tags: