Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用拓扑排序怎么错了,找不出来啊,求教TT,求改

Posted by tang123 at 2015-04-30 10:57:00 on Problem 1949
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int maxn=10005;
vector<int> map[maxn];
int in[maxn];
int step[maxn];
int used[maxn];
int ff[maxn];
int a[maxn];
int father[maxn];
int N,u,cnt_zero,sum;
void Init()
{
    for(int i=1 ; i <=N ; i++)
    father[i]=i;
    memset(step,0,sizeof(step));
    memset(in,0,sizeof(in));
    memset(used,0,sizeof(used));
    cnt_zero=sum=0;
}
int find_(int x)
{
    if(x==father[x]) return x;
    return father[x]=find_(father[x]);
}
void Union(int x,int y)
{
    x=find_(x);
    y=find_(y);
    if(x!=y)
    father[x]=y;
}
void find_dz(int ii)
{
    int i;
    u=0;
    for(i=1 ; i <= N ; i++)
    {
        if(in[i]==0 && used[i]==0 && find_(i)==ii )
        {
            step[u++]=i;
            cnt_zero++;
        }
    }
    if(u!=0)
    {
        int mm=-1;
        for(i=0 ; i < u ; i++)
        {
            if(a[step[i]]>mm)
                mm=a[step[i]];
        }
        if(mm!=-1)
        {
            sum+=mm;
        }
    }
}
void cut(int v)
{
    used[v]=1;
    for(int i=0 ; i < map[v].size() ; i++)
    {
        in[map[v][i]]--;
    }
}
void topsort(int ii)
{
    int i,j;
    for(i=1; i <= N ; i++)
    {
        find_dz(ii);
        for(j=0; j < u ; j++)
        {
            cut(step[j]);
        }
    }
}

int main()
{
    int i,n,t,j,m;
    while(scanf("%d",&N)!=EOF)
    {
        Init();
        for(i=1; i <= N ; i++)
        {
            map[i].clear();
            scanf("%d%d",&t,&n);
            a[i]=t;
            for(j=0; j<n; j++)
            {
                scanf("%d",&m);
                Union(i,m);
                map[m].push_back(i);
                in[i]++;
            }
        }
        int minn=-1;
        for(i=1 ; i <= N ; i++)
        {
            sum=0;
            if(father[i]==i)
            {
                topsort(i);
                if(sum>minn)
                minn=sum;
            }
        }
        for(i=1 ; i <= N ; i++)
        if(minn<a[i])
        minn=a[i];
        printf("%d\n",minn);
    }
    return 0;
}
/*
5
4 0
2 1 1
2 1 2
3 0
5 1 4


*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator