Ice_cream’s world II

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2453    Accepted Submission(s): 574

3 1
0 1 1

4 4
0 1 10
0 2 10
1 3 20
2 3 30

impossible

40 0

//408K	2665 B
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 10007
#define inf 0x3f3f3f
using namespace std;
int pre[M],vis[M],id[M];
int in[M];
int n,m,ansi;

struct Node//建立邻接表
{
    int u,v;
    int cost;
}E[M*M+5];

int direct_mst(int root,int nv,int ne)
{
    int ret=0;
    while(true)
    {
        //找最小入边
        for(int i=0;i<nv;i++)
            in[i]=inf;
        for(int i=0;i<ne;i++)
        {
            int u=E[i].u;
            int v=E[i].v;
            if(E[i].cost<in[v]&&u!=v)
            {
                pre[v]=u;
                if(u==root)
                    ansi=i;
                in[v]=E[i].cost;
            }
        }
        for(int i=0;i<nv;i++)
        {
            if(i==root)continue;
            if(in[i]==inf)return -1;
        }
        //找环
        int cntnode=0;
        memset(id,-1,sizeof(id));
        memset(vis,-1,sizeof(vis));
        in[root]=0;
        for(int i=0;i<nv;i++)//标记每个环
        {
            ret+=in[i];
            int v=i;
            while(vis[v]!=i&&id[v]==-1&&v!=root)
            {
                vis[v]=i;
                v=pre[v];
            }
            if(v!=root&&id[v]==-1)
            {
                for(int u=pre[v];u!=v;u=pre[u])
                {
                    id[u]=cntnode;
                }
                id[v]=cntnode++;
            }
        }
        if(cntnode==0)break;//无环
        for(int i=0;i<nv;i++)
            if(id[i]==-1)
                id[i]=cntnode++;
        //缩点，重新标记
        for(int i=0;i<ne;i++)
        {
            int v=E[i].v;
            E[i].u=id[E[i].u];
            E[i].v=id[E[i].v];
            if(E[i].u!=E[i].v)
            {
                E[i].cost-=in[v];
            }
        }
        nv=cntnode;
        root=id[root];
    }
    return ret;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int u,v,w,sum=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            E[i].u=++u;
            E[i].v=++v;
            if(u!=v)
                E[i].cost=w;
            else
                E[i].cost=inf;
            sum+=w;
        }
        sum++;
        for(int i=0;i<n;i++)
        {
            E[m+i].u=0;
            E[m+i].v=i+1;
            E[m+i].cost=sum;
        }
        int ans=direct_mst(0,n+1,m+n);//n代表点的个数，m代表边的个数
        if(ans==-1||ans-sum>=sum)
            printf("impossible\n");//无法生成最小树形图
        else
            printf("%d %d\n",ans-sum,ansi-m);
        printf("\n");
    }
    return 0;
}

Ice_cream’s world III

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 657    Accepted Submission(s): 213

2 1
0 1 10

4 0

10

impossible

//125MS	344K
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int pre[1007];
struct E
{
    int u,v,w;
}edg[1007*100];
int cmp(E a,E b)
{
    return a.w<b.w;
}
int find(int x)
{
    while(x!=pre[x])
        x=pre[x];
    return x;
}
void unio(int a,int b)
{
    int x=find(a);
    int y=find(b);
    if(x==y)return;
    pre[x]=y;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int sum=0,edge=1;
        for(int i=0;i<=1000;i++)pre[i]=i;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w);
        }
        sort(edg,edg+m,cmp);
        for(int i=0;i<m;i++)
        {
            if(find(edg[i].u)!=find(edg[i].v))
            {
                edge++;//边的个数
                sum+=edg[i].w;
                unio(edg[i].u,edg[i].v);
            }
        }
        int flag=0;
        if(edge!=n)printf("impossible\n\n");
        else printf("%d\n\n",sum);
    }
    return 0;
}