ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1416. Confidential

WA34,I don't konw why-_-
Posted by zslwyuan 12 Dec 2011 16:03
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef struct qwer{int x,y,pr;}B;
B E[1000000];
int sec,fir,goal;
bool used[1000000];
bool ar[501];
int jl[501],n;
int dis[501][501];
bool cmp(B a,B b)
{
    return a.pr<b.pr;
}
int map[501][501];
int jg[501][501];
int ft[502];
int ance[501][501];
int find(int x)
{
    if (x==ft[x])return x;
    return ft[x]=find(ft[x]);
}

void check(int now,int ft,int l)
{
    int i;
    for (i=1;i<=jl[0];i++)
    {
        if (now==jl[i])continue;
        if (l>dis[ft][jl[i]])
            dis[now][jl[i]]=dis[jl[i]][now]=l;
        else
            dis[now][jl[i]]=dis[jl[i]][now]=dis[ft][jl[i]];
    }
    jl[0]++;jl[jl[0]]=now;
    for (i=1;i<=map[now][0];i++)
    {
        if (map[now][i]==ft)continue;
        check(map[now][i],now,jg[now][i]);
    }
    jl[0]--;
}

void LCA(int now,int b)
{
    int i;ar[now]=1;
    for (i=1;i<=map[now][0];i++)
    {
        if (map[now][i]==b)continue;
        LCA(map[now][i],now);
        ft[find(map[now][i])]=now;
    }
    for (i=1;i<=n;i++)
    if (ar[i]&&i!=now)
    {
        ance[now][i]=ance[now][i]=find(i);
    }
}

int main()
{
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    int i,j,k,l,m;
    scanf("%d %d\n",&n,&m);
    memset(used,0,sizeof(used));
    for (i=1;i<=m;i++)
        scanf("%d %d %d\n",&E[i].x,&E[i].y,&E[i].pr);
    sort(E+1,E+1+m,cmp);
    int fini=0;
    int ans1=0,ans2=0;
    memset(map,0,sizeof(map));
    for (i=1;i<=n;i++)ft[i]=i;
    for (i=1;i<=m;i++)
    {
        int x=find(E[i].x),y=find(E[i].y);
        if (x!=y)
        {
            fini++;
            used[i]=1;
            ans1+=E[i].pr;
            map[E[i].x][++map[E[i].x][0]]=E[i].y;
            jg[E[i].x][map[E[i].x][0]]=E[i].pr;
            map[E[i].y][++map[E[i].y][0]]=E[i].x;
            jg[E[i].y][map[E[i].y][0]]=E[i].pr;
            ft[y]=x;
            if (fini==n-1)break;
        }
    }
    if (fini<n-1){printf("Cost: -1\nCost: -1\n");return 0;}
    if (m==n-1){printf("Cost: %d\nCost: -1\n",ans1);return 0;}
    ans2=~0u>>1;
    memset(jl,0,sizeof(jl));
    jl[0]=0;
    memset(dis,-1,sizeof(dis));
    check(1,0,-1);
    memset(ar,0,sizeof(ar));
    for (i=1;i<=n;i++)ft[i]=i;
    LCA(1,-1);
    for (i=1;i<=m;i++)
    {
        if (used[i])continue;
        int wh=ance[E[i].x][E[i].y];
        int bone=max(dis[wh][E[i].x],dis[wh][E[i].y]);
        if (ans1-bone+E[i].pr<ans2)
        ans2=ans1-bone+E[i].pr;
    }
    printf("Cost: %d\nCost: %d\n",ans1,ans2);
    return 0;
}
Re: WA34,I don't konw why-_-
Posted by Busarov Viacheslav [Barnaul] 5 Sep 2012 16:14
4 4
1 2 4
2 3 3
3 4 2
2 4 10

answer:
  Cost: 9
  Cost: 16