| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5439 |
2014-05-02T10:25:54 Z |
gs12117 |
Toll (APIO13_toll) |
C++ |
|
2500 ms |
7344 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[23];
edge eipb[300100];
int uft[100100];
long long int pnb[100100];
int cprs[100100];
long long int pn[23];
long long int npn[23];
int neb[23][2];
int nebn;
int chk[300100];
int ufs[23];
int es[23];
int elist[45][2];
int price[23];
int bchk[23];
long long int snum[23];
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[i]=0;
}
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][1]+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);
}
}
for(i=0;i<m;i++){
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,tn,tm;
scanf("%d%d%d",&n,&m,&p);
for(i=0;i<m;i++){
scanf("%d%d%d",&eipb[i].a,&eipb[i].b,&eipb[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",&pnb[i]);
}
std::sort(eipb,eipb+m);
for(i=1;i<=n;i++){
uft[i]=i;
}
for(i=0;i<p;i++){
if(uftf(etob[i][0])!=uftf(etob[i][1]))uft[uftf(etob[i][0])]=uftf(etob[i][1]);
}
for(i=0;i<m;i++){
chk[i]=0;
if(uftf(eipb[i].a)!=uftf(eipb[i].b)){
uft[uftf(eipb[i].a)]=uftf(eipb[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(eipb[i].a)]=uftf(eipb[i].b);
}
}
tn=0;
for(i=1;i<=n;i++){
if(cprs[uftf(i)]==0){
tn++;
cprs[uftf(i)]=tn;
}
}
for(i=1;i<=n;i++){
pn[cprs[uftf(i)]]+=pnb[i];
}
for(i=0;i<p;i++){
etob[i][0]=cprs[uftf(etob[i][0])];
etob[i][1]=cprs[uftf(etob[i][1])];
}
for(i=0;i<m;i++){
eipb[i].a=cprs[uftf(eipb[i].a)];
eipb[i].b=cprs[uftf(eipb[i].b)];
}
tm=0;
for(i=1;i<=tn;i++){
uft[i]=i;
}
for(i=0;i<m;i++){
if(uftf(eipb[i].a)!=uftf(eipb[i].b)){
eip[tm]=eipb[i];
tm++;
uft[uftf(eipb[i].a)]=uftf(eipb[i].b);
}
}
n=tn;
m=tm;
for(i=1;i<(1<<p);i++){
calc(i);
}
printf("%lld",ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
7344 KB |
Output is correct |
| 2 |
Correct |
276 ms |
7344 KB |
Output is correct |
| 3 |
Correct |
272 ms |
7344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2500 ms |
7340 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
