2016寒假集训队第五次作业

题解

Problem A:确定比赛名次

题意：判断入度为0的点的个数是否唯一。

题解：拓扑排序：
　 (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。
　　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边。
　　(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止。
　　
参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ans[510][510],n,in[510],queue[510],a,b,m,top,k;
int main()
{
    while (cin>>n>>m)
    {
        top=0;
        k=0;
        memset(in,0,sizeof(in));
        memset(ans,0,sizeof(ans));
        for (int i=0; i<m; i++)
        {
            cin>>a>>b;
            if(ans[a][b]==0)
            {
                ans[a][b]=1;
                in[b]++;
            }
        }
        for (int j=0; j<n; j++)
        {
            for (int i=1; i<=n; i++)
            {
                if (in[i]==0)
                {
                    top=i;
                    break;
                }
            }
            queue[k]=top;
            k++;
            in[top]=-1;
            for (int i=1; i<=n; i++)
            {
                if (ans[top][i])
                    in[i]--;
            }
        }
        for (int i=0; i<k-1; i++)
            cout<<queue[i]<<" ";
        cout<<queue[n-1]<<endl;
    } 
    return 0;
}

Problem B:Reward

题意：n个人，m条边，每条边a，b 表示a比b的工资多1，每个人的工资至少888，问你工资和至少多少？如果出现矛盾关系，输出-1。

题解：根据人的工资关系建立拓扑图，工资尽量从888开始，然后根据是否能全部排好序判断是出现矛盾关系。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int n,m,ans[10010],r[10010],s,d,sum,a,b;
vector <vector <int> > v;
int main()
{
    while(cin>>n>>m)
    {
        v.clear();
        v.resize(n+1);
        for (int i=0; i<=n; i++)
        {
            ans[i]=-1;
            r[i]=0;
        }
        while (m>0)
        {
            m--;
            cin>>a>>b;
            v[b].push_back(a);
            r[a]++;
        }
        queue <int> q;
        for (int i=1; i<=n; i++)
        {
            if(r[i]==0) q.push(i);
        }
        int tmp=888;
        while (!q.empty())
        {
            int l=q.size();
            while (l>0)
            {
                l--;
                s=q.front();
                q.pop();
                ans[s]=tmp;
                for (int i=0; i<v[s].size(); i++)
                {
                    d=v[s][i];
                    r[d]--;
                    if (r[d]==0) q.push(d);
                }
            }
            tmp++;
        }
        sum=0;
        for (int i=1; i<=n; i++)
        {
            if (ans[i]>0) sum+=ans[i];
            else
            {
                sum=-1;
                break;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

Problem D:欧拉回路

题意：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？若欧拉回路存在则输出1，否则输出0。

题解：由题意可知，这是一个无向图，无向图存在欧拉回路需要满足两个条件：
　　1：底图是连通的，可用并查集判断。
　　2：不存在度数为奇数的点。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1100],fa[1100],e,v;
int find(int x)
{
    if (x==fa[x]) return x;
    else
    {
        int r=find(fa[x]);
        fa[x]=r;
        return r;
    }
}
void join(int x, int y)
{
    int fx=find(x),fy=find(y);
    if (fx!=fy) fa[fx]=fy;
}
int iseuler()
{
    for (int i=1; i<=v; i++)
        if (a[i]&1) return 0;
    return 1;
}
int isConnct()
{
    int cnt=0;
    for (int i=1; i<=v; i++)
        if (fa[i]==i) cnt++;
    if (cnt==1) return 1;
    return 0;
}
int main()
{
    while(cin>>v)
    {
        if (v==0) break;
        cin>>e;
        memset(a,0,sizeof(a));
        for (int i=1; i<=1010; i++)
            fa[i]=i;
        for (int i=1; i<=e; i++)
        {
            int from,to;
            cin>>from>>to;
            a[from]++;
            a[to]++;
            join(from,to);
        }
        //cout<<11111<<endl;
        if (isConnct() && iseuler()) cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}