首页 > 代码库 > URAL(timus)1709 Penguin-Avia(并查集)
URAL(timus)1709 Penguin-Avia(并查集)
Penguin-Avia
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
The Penguin-Avia airline, along with other Antarctic airlines, experiences financial difficulties because of the world‘s economic crisis. People of Antarctica economize on flights and use trains or prefer to stay at home. The airline‘s management hopes that the number of their clients will increase in the summer due to the tourists visiting the coastal resorts. In order to hold out till the summer, it was decided to optimize the flight scheme by cancelling some flights and introducing some new flights.
Director of Penguin-Avia assumes that after the optimization the flight scheme must have the following properties:
- Using one or more Penguin-Avia flights, one can get from any Antarctic airport to any other.
- The scheme must contain the minimal number of flights among all the schemes satisfying the first property.
Help Director of Penguin-Avia transform the existing flight scheme spending as little money as possible. For doing that, you will be presented with a travel card for all flights of the airline.
Input
In the first line you are given the number n of airports in Antarctica, 2 ≤ n ≤ 100. In the second line you are given the integers d and a, 1 ≤ d, a ≤ 106. The following n lines describe the existing scheme of Penguin-Avia flights in the form of an n × n matrix. There is “1” in a cell (i, j) of the matrix if the airline has flights between the airports i and j. Otherwise, there is “0” in the cell. It is guaranteed that the matrix is symmetric and there are only zeros on its diagonal.
Output
In the first line output the minimal amount of money necessary for the optimization of the existing flight scheme. In the next n lines give the plan of changing the scheme in the form of an n × n matrix. A cell (i, j) of this matrix contains the symbol “d” if the flights between the airports i and j should be cancelled. In the case when a new flight should be introduced between these airports, the cell contains the symbol “a”. The remaining cells contain the symbol “0”. The matrix must be symmetric. If there are several optimal schemes, output any one of them.
Sample
input | output |
---|---|
62 3011000101000110000000011000101000110 | 70d0000d00000000a0000a0d0000d00000000 |
Problem Author: Alexander Ipatov
【分析】给出一个图,双向的,现要你删除,添加一些边,使得所有点联通,删除,添加都需要费用,问你最小费用是多少。就是个简 单的并查集问题。
#include <iostream>#include <cstring>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <time.h>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#define inf 0x3f3f3f3f#define mod 10000typedef long long ll;using namespace std;const int N=105;const int M=50000;int power(int a,int b,int c){int ans=1;while(b){if(b%2==1){ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}char w[N][N];int vis[N][N],VIS[N][N];int n,m,k,c;ll s=0;int parent[N];int Find(int x){ if(parent[x]!=x)parent[x]=Find(parent[x]); return parent[x];}void Union(int x,int y){ x=Find(x);y=Find(y); if(x==y)return; parent[y]=x;}int main(){ for(int i=0;i<=100;i++)parent[i]=i; int a,d; scanf("%d%d%d",&n,&a,&d); for(int i=1;i<=n;i++){ scanf("%s",w[i]+1); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(w[i][j]==‘1‘){ int x=Find(i); int y=Find(j); if(x==y)vis[i][j]=vis[j][i]=1,s+=a; else Union(i,j); } } } int ok=Find(1); for(int i=2;i<=n;i++){ int x=Find(i); if(x!=ok&&vis[1][i]!=2)vis[1][i]=vis[i][1]=2,s+=d,Union(1,i); } printf("%lld\n",s); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int x=Find(i); int y=Find(j); if(!vis[i][j])printf("0"); else if(vis[i][j]==1)printf("d"); else if(vis[i][j]==2)printf("a"); } printf("\n"); } return 0;}
URAL(timus)1709 Penguin-Avia(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。