## 10600 - ACM Contest and Blackout

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

New poster
Posts: 2
Joined: Wed Feb 18, 2004 5:50 am

### 10600 - ACM Contest and Blackout

Im getting WA on this one. here is a description of my algorithm:

I use kruskal to calculate the MST. then for each edge in the solution recalculate MST without that edge. so the first solution is the one given by kruskal and the second on is the min among the other solutions.

Is this ok?

sorry about my english....

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Right

Your method looks similar to mine.
The key part was to remove edges only from the MST and not the other edges. From your post it looks like you have considered that too.

Maybe you made a minor mistake in your coding.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

check out
coremen(CLRS) for
"second best minimum tree"
in the chapter
"minimum spanning tree."
--
Anupam
"Everything should be made simple, but not always simpler"

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Hello!
I think i solve this problem,my program works right for symple inputs ,but gets WA.Can somebody give me any input and output.
Thanks before.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
I passed the example test data, but also got WA first time.
Turned out there is a problem when the graph is not connected (it happens when trying to find the second minimum value).
I fixed that and now it is AC. Try this:

Input:

Code: Select all

``````1
4 4
1 4 5
1 2 2
2 3 3
1 3 4
``````
Output:

Code: Select all

``````10 11
``````

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I hade already find the problem with graph not connectivity,but your test help me to find that my program is getting not WA but RE(for Pascal Online Judge is giving WA instade of RUN-TIME ERROR).I fix and got AC.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

### 10600

I can't understand why do I keep getting WA's on 10600, while it look's an easy problem with Kruskal algorithm.
[cpp]
AC
[/cpp]
Last edited by mlvahe on Thu Aug 26, 2004 4:36 pm, edited 1 time in total.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Hello Vahe.
Did you watch case when graph is not connected.
What is your answer for this test case.
Input

Code: Select all

``````1
4 4
1 4 5
1 2 2
2 3 3
1 3 4 ``````
Output

Code: Select all

``````10 11
``````
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia
Hi Eduard.
Yes, I have considered that case.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
A really small mistake. It also took a while before I saw it. Look at this lines:
[cpp]for (i = 0; i < n; i++)
used = 0;[/cpp]
(should be i<m of course)

mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia
Hi krijger.

Thank you very very much.
I got AC.

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

### 10600, i have got wa for n times!

can anyone tell me what's wrong?
[cpp]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Tedge{
int u,v;
}e[20010],mt[110];
int n,m,tot,ans1,ans2,totcase;
int g[110][110],opt[110][110];
bool mark[110][110];

int cmp(const void *a,const void *b){
Tedge *e1=(Tedge*)a,*e2=(Tedge*)b;
return e1->u-e2->u;
}

inline int max(int a,int b){
return a>b?a:b;
}

inline int min(int a,int b){
return a<b?a:b;
}

void bfs(int v)
{
int i,cl,op,low,now;
int que[110];
bool use[110];

memset(use,false,sizeof(use));
que[0]=v,use[v]=true;
cl=0,op=1;
while (cl<op){
now=que[cl];
for (low=0;low<tot;low++)
if (mt[low].u==now) break;
for (i=low;mt.u==now;i++)
if (!use[mt.v]){
que[op++]=mt.v;
use[mt.v]=true;
opt[v][mt.v]=max(opt[v][now],g[now][mt.v]);
}
cl++;
}
}

void solve()
{
int i,j,minv,u,v;
int dis[110],pre[110];
bool vis[110];

for (i=2;i<=n;i++) pre=1,dis=g[1],vis=false;
dis[1]=0,vis[1]=true;
for (i=2;i<=n;i++){
minv=-1;
for (j=1;j<=n;j++)
if (!vis[j]&&dis[j]>0)
if (minv==-1||dis[j]<dis[minv]) minv=j;
mt[tot].u=pre[minv],mt[tot].v=minv; tot++;
mt[tot].u=minv,mt[tot].v=pre[minv]; tot++;
mark[pre[minv]][minv]=mark[minv][pre[minv]]=true;
ans1+=dis[minv];
vis[minv]=true;
for (j=1;j<=n;j++)
if (g[minv][j]>0&&(!vis[j])&&(dis[j]==0||dis[j]>g[minv][j]))
pre[j]=minv,dis[j]=g[minv][j];
}

ans2=1000000000;
qsort(mt,tot,sizeof(Tedge),cmp);
for (i=1;i<=n;i++) bfs(i);
for (i=0;i<m;i++){
u=e[i].u,v=e[i].v;
if (!mark[v]) ans2=min(ans2,ans1+g[v]-opt[v]);
}
}

int main()
{
int i,u,v,cost;

scanf("%d",&totcase);
while (totcase--){
memset(g,0,sizeof(g));
memset(opt,0,sizeof(opt));
memset(mark,false,sizeof(mark));

scanf("%d%d",&n,&m);
for (i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&cost);
e[i].u=u,e[i].v=v;
g[v]=g[v]=cost;
}
tot=ans1=ans2=0;
solve();
printf("%d %d\n",ans1,ans2);
}
return 0;
}
[/cpp]

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### 10600 ACM contest and Blackout

Salamo Aleko.
I solve it using prime algorithm and got ac in 0.086s.....
And now after coding it with kruskal algorithm using "Union with path compression path" I get wrong answer. I can not find any logical reason
for this.....Can any one help me .......Thanks in advace.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### kruskal..

I solved this problem using kruskal.

So, there must be some minor mistake in your kruskal implementation.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Salamo Aleko
Finally I detect this minor Mistake and get accepted in 0.184
Is this good time or ....
Thanx......
http://acm.uva.es/problemset/usersjudge.php?user=8957CA