10600 - ACM Contest and Blackout

[SupeRaskao]

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]

Hi SupeRaskao,

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]

check out
coremen(CLRS) for
"second best minimum tree"
in the chapter
"minimum spanning tree."
hope it will help you.
--
Anupam

[Eduard]

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.

[shuniu]

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]

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.

[mlvahe]

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]

[Eduard]

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

[mlvahe]

Hi Eduard.
Yes, I have considered that case.

[krijger]

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]

Hi krijger.

Thank you very very much.
I got AC.

[zzzzzddddd]

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]

Salamo Aleko.
I have some thing strange about this problem
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]

I solved this problem using kruskal.

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

[898989]

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