| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5435 |
2014-05-02T08:35:15 Z |
gs12117 |
Toll (APIO13_toll) |
C++ |
|
0 ms |
9300 KB |
#include<stdio.h>
#include<algorithm>
int n,p,m;
int etob[23][2];
long long int ans;
struct edge{
int a,b,cost;
bool operator<(const edge&r)const{
return cost<r.cost;
}
};
edge eip[300100];
int uft[100100];
long long int pn[100100];
long long int npn[100100];
int neb[23][2];
int nebn;
int chk[300100];
int ufs[100100];
int es[100100];
int elist[45][2];
int price[23];
int bchk[100100];
int snum[100100];
long long int nans;
int uftf(int x){
if(x==uft[x])return x;
return uft[x]=uftf(uft[x]);
}
void fillpath(int x,int y,int val){
int i;
bchk[x]=1;
if(x==y)return;
for(i=es[x];i<es[x+1];i++){
if(bchk[elist[i][0]]==0){
fillpath(elist[i][0],y,val);
if(bchk[y]==1){
if(price[elist[i][1]]>val)price[elist[i][1]]=val;
return;
}
}
}
}
void dfs(int x){
int i;
bchk[x]=1;
snum[x]=npn[x];
for(i=es[x];i<es[x+1];i++){
if(bchk[elist[i][0]]==0){
dfs(elist[i][0]);
snum[x]+=snum[elist[i][0]];
nans+=snum[elist[i][0]]*elist[i][1];
}
}
}
void calc(int x){
int i,j;
for(i=1;i<=n;i++){
uft[i]=i;
}
for(i=0;i<p;i++){
if((x>>i)%2==1){
if(uftf(etob[i][0])==uftf(etob[i][1]))return;
uft[uftf(etob[i][0])]=uftf(etob[i][1]);
}
}
for(i=0;i<m;i++){
chk[i]=0;
if(uftf(eip[i].a)!=uftf(eip[i].b)){
uft[uftf(eip[i].a)]=uftf(eip[i].b);
chk[i]=1;
}
}
for(i=1;i<=n;i++){
uft[i]=i;
}
for(i=0;i<m;i++){
if(chk[i]==1){
uft[uftf(eip[i].a)]=uftf(eip[i].b);
}
}
for(i=1;i<=n;i++){
npn[uftf(i)]+=pn[i];
ufs[i]=uftf(i);
}
nebn=0;
for(i=0;i<p;i++){
if((x>>i)%2==1){
neb[nebn][0]=uftf(etob[i][0]);
neb[nebn][1]=uftf(etob[i][1]);
price[nebn]=999999999;
nebn++;
}
}
for(i=0;i<n+3;i++){
es[i]=0;
}
for(i=0;i<nebn;i++){
es[neb[i][0]+2]++;
es[neb[i][1]+2]++;
}
for(i=0;i<n+3;i++){
es[i+1]+=es[i];
}
for(i=0;i<nebn;i++){
elist[es[neb[i][0]+1]][0]=neb[i][1];
elist[es[neb[i][0]+1]][1]=i;
es[neb[i][0]+1]++;
elist[es[neb[i][1]+1]][0]=neb[i][0];
elist[es[neb[i][0]+1]][1]=i;
es[neb[i][1]+1]++;
}
for(i=1;i<=n;i++){
uft[i]=i;
}
for(i=0;i<m;i++){
if(chk[i]==1){
uft[uftf(eip[i].a)]=uftf(eip[i].b);
}
else if(uftf(eip[i].a)!=uftf(eip[i].b)){
for(j=1;j<=n;j++){
bchk[j]=0;
}
fillpath(ufs[eip[i].a],ufs[eip[i].b],eip[i].cost);
uft[uftf(eip[i].a)]=uftf(eip[i].b);
}
}
for(i=0;i<2*nebn;i++){
elist[i][1]=price[elist[i][1]];
}
for(j=1;j<=n;j++){
bchk[j]=0;
snum[j]=0;
}
nans=0;
dfs(ufs[1]);
if(ans<nans)ans=nans;
}
int main(){
int i,j;
scanf("%d%d%d",&n,&m,&p);
for(i=0;i<m;i++){
scanf("%d%d%d",&eip[i].a,&eip[i].b,&eip[i].cost);
}
for(i=0;i<p;i++){
scanf("%d%d",&etob[i][0],&etob[i][1]);
}
for(i=1;i<=n;i++){
scanf("%lld",&pn[i]);
}
std::sort(eip,eip+m);
for(i=1;i<(1<<p);i++){
calc(i);
}
printf("%lld",ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
9300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
