POJ - 3538 - Domestic Networks
先上题目:
Time Limit: 2000MS | Memory Limit: 65536K | |||
Total Submissions: 732 | Accepted: 204 | Special Judge |
Description
Alex is a system administrator of Domestic Networks Inc. His network connects apartments and spans over multiple buildings.
The network expands and Alex has to design a new network segment. He has a map that shows apartments to connect and possible links. Each link connects two apartments and for each possible link its length is known. The goal is to make all apartments connected (possibly through other apartments).
Domestic Networks Inc. buys cable in the nearest cable shop. Unfortunately, shop sells only category 5 and 6 cables at price of p5 and p6 rubles per meter respectively. Moreover, there are only q5 meters of category 5 cable and q6 meters of category 6 cable available in the shop.
Help Alex to solve a hard problem: make a new network construction plan with possible minimal cost. A plan consists of list of links to be made and cable category for each link (each link should be a single piece of cable of either 5 or 6 category). The cost of the plan is the sum of cost of all cables. The total length of cables of each category used in the plan should not exceed the quantity of the cable available in the shop.
Input
The first line of the input file contains two numbers: n — the number of apartments to be connected and m — the number of possible links (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000).
Following m lines contain possible link descriptions. Each description consists of three integer numbers: ai and bi — apartments that can be connected by the link and li — link length in meters (0 ≤ li ≤ 100). Apartments are numbered from 1 to n.
The last line of the input file contains four integer numbers: p5, q5, p6 and q6 — price and quantity of category 5 and 6 cables respectively (1 ≤ pi, qi ≤ 10 000).
Output
If all apartments can be connected with the available cable, output n lines — an optimal network construction plan. The first line of the plan must contain plan’s cost. Other lines of the plan must consist of two integer numbers each: ai — number of the link to make and ci — the category of the cable to make it of. Links are numbered from 1 to m in the order they are specified in the input file. If there are more than one optimal plans, output any of them.
If there is no plan meeting all requirements, output a single word “Impossible”.
Sample Input
6 7
1 2 7
2 6 5
1 4 8
2 3 5
3 4 5
5 6 6
3 5 3
2 11 3 100
Sample Output
65
1 5
2 6
4 6
5 6
7 5
Source
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define MAX 10002
using namespace std; typedef struct edge{
int u,v,l,id; bool operator < (const edge& o)const{
return l<o.l;
}
}edge; edge e[MAX];
int p[MAX],mst[MAX],tot;
int n,m,p5,q5,p6,q6,i5,i6;
int pag[MAX];
bool f[MAX];
set<int> e5,e6; int findset(int u){
return u==p[u] ? p[u] : p[u]=findset(p[u]);
} void MST(){
tot=;
int u,v;
for(int i=;i<m;i++){
u=findset(e[i].u); v=findset(e[i].v);
if(p[u]!=p[v]){
p[v]=u;
mst[tot++]=i;
}
}
} int main()
{
int I5,I6;
//freopen("data.txt","r",stdin);
while(scanf("%d %d",&n,&m)!=EOF){
for(int i=;i<=n;i++) p[i]=i;
for(int i=;i<m;i++){
scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].l);
e[i].id=i+;
}
scanf("%d %d %d %d",&p5,&q5,&p6,&q6);
i5=; i6=;
if(p5>p6){
swap(p5,p6);
swap(q5,q6);
swap(i5,i6);
}
sort(e,e+m);
MST();
if(tot!=n-){
printf("Impossible\n");
continue;
} /*********pag*********/
memset(f,,sizeof(f));
e5.clear(); e6.clear();
//memset(pag,0,sizeof(pag));
f[]=;
for(int i=;i<tot;i++){
int l=e[mst[i]].l;
e6.insert(mst[i]);
for(int j=q5;j>=l;j--){
if(!f[j] && f[j-l]){
f[j]=;
pag[j]=mst[i];
}
}
}
int k=q5;
while(!f[k]) k--;
while(k>){
e5.insert(pag[k]);
e6.erase(pag[k]);
k-=e[pag[k]].l;
}
I5=I6=;
for(set<int>::iterator it = e5.begin();it!=e5.end();it++){
I5+=e[*it].l;
}
for(set<int>::iterator it = e6.begin();it!=e6.end();it++){
I6+=e[*it].l;
}
if(I5<=q5 && I6<=q6){
printf("%d\n",I5*p5+I6*p6);
for(set<int>::iterator it = e5.begin();it!=e5.end();it++){
printf("%d %d\n",e[*it].id,i5);
}
for(set<int>::iterator it = e6.begin();it!=e6.end();it++){
printf("%d %d\n",e[*it].id,i6);
}
}else{
printf("Impossible\n");
}
}
return ;
}
/*3538*/
最新文章
- css响应式布局RWD
- 转!java基础笔记
- mysql grant ,User,revoke
- C++日志操作开源函数库之Google-glog
- awk 两列相减
- theano log softmax 4D
- [HMLY]7.iOS MVVM+RAC 从框架到实战
- 工作中遇到的http返回码
- .net面试题【持续更新.....】
- nginx.conf完整配置实例
- 一个C#操作RabbitMQ的完整例子
- windows下如何创建没有名字的.htaccess文件
- RAID卡技术简析
- SpringBoot中使用JNnit4(入门篇)
- 如何引入iconfont图标与Element-UI组件
- 20个可用于商业用途的免费 CC0 授权的高分辨率图库
- POJ 2248 - Addition Chains - [迭代加深DFS]
- docker容器与镜像
- HADOOP实战
- lepus部署