CQUPT 集训队专题训练（拓扑排序/欧拉路）

拓扑排序/欧拉路

A - 确定比赛名次
题意：

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。给出一个符合要求的排名。

解题思路：

拓扑排序：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。将入度为0的点一一保存在数组中。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int a[510][510],b[510],ans[510];
int main()
{
    int n,m,p1,p2;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&p1,&p2);
            if(a[p1][p2]==0)
            b[p2]++;
            a[p1][p2]=1;
        }
        int num=0;
        int t;
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(b[j]==0)
                {
                    t=j;
                    ans[num++]=t;
                    b[j]--;
                    break;
                }
            }
            for(int j=1;j<=n;j++)
            {
                if(a[t][j]==1)
                b[j]--;
            }
        }
        for(int i=0;i<n-1;i++)
         printf("%d ",ans[i]);
        printf("%d\n",ans[n-1]);
    }
    return 0;
}

B - Reward
题意：

n个工人，m个要求(n<=10000,m<=20000)，每个要求输出a,b表示a的奖金要比b的高，求出满足所有要求后，老板所要发的奖金的最少。

解题思路：

由于发的奖金的金额是按照梯度进行递增的，需要拓扑排序排在后面的奖金要比其相邻的前面的奖金要多1，才能满足老板发的奖金最少，用前向星维护相连的边，用队列来维护入度为0的顶点，再出队列时，用sum求奖金和。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<queue>
#define maxx 10005
using namespace std;
int n,sum,ans;
int in[maxx],head[maxx],mon[maxx];
struct Node
{
    int to;
    int next;
}edge[2*maxx];
void solve()
{
    int v;
    queue<int>Q;
    for(int i=1;i<=n;i++)
    if(in[i]==0)
    Q.push(i);
    while(!Q.empty())
    {
        v=Q.front();
        sum+=mon[v];
        Q.pop();
        ans++;
        for(int i=head[v];i!=-1;i=edge[i].next)
        {
            if(--in[edge[i].to]==0)
            Q.push(edge[i].to);
            mon[edge[i].to]=mon[v]+1;
        }
    }
}
int main()
{
    int m,a,b,tot;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++)
        mon[i]=888;
        tot=0;
        sum=0;
        ans=0;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            edge[tot].to=a;
            edge[tot].next=head[b];
            head[b]=tot++;
            in[a]++;
        }
    //  for(int i=1;i<=n;i++)
    //  cout<<head[i]<<endl;
        solve();
        if(ans!=n)
        sum=-1;
        cout<<sum<<endl;
    }
    return 0;
}

D - 欧拉回路
题意：

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

解题思路：

欧拉回路必须保证这条路联通，用并查集判断图的连通性，然后图中所有节点度均为偶数。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int in[1005],fa[1005];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int a,int b)
{
    int aa=find(a);
    int bb=find(b);
    if(aa!=bb)
    {
        fa[bb]=aa;
    }
}
int main()
{
    int n,m;
    int a,b;
    while(scanf("%d",&n)!=EOF&&n)
    {
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++)
        fa[i]=i;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            unite(a,b);
            in[a]++;
            in[b]++;
        }
        int flag=1;
        int temp=fa[1];
        for(int i=1;i<=n;i++)
        {
            if(fa[i]!=temp)
            flag=0;
            if(in[i]%2!=0)
            flag=0;
        }
        cout<<flag<<endl;
//
    }
    return 0;
}

E - Play on Words
题意：

给出N个单词(1 <= N <= 100000)，判断是否满足一种排序，使得前一个单词的最后一个字母与后一个单词的第一个字母相同。

解题思路：

将每个单词的首尾当作图的顶点，判断是否为欧拉通路：图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1。用并查集判断图是否联通，记录出度入度情况，最后判断是否为欧拉通路

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int fa[30],rank[30];
int in[30],out[30];
bool ex[30];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Union(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy)
    {
    /*  if(rank[xx]>rank[yy])
        fa[yy]=xx;
        else 
        {
            if(rank[xx]==rank[yy])
            rank[yy]++;
            fa[xx]=yy;
        }
        */
        fa[yy]=xx;
    }
}
int main()
{
    int t;
    char word[1024];
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<26;i++)
        {
            in[i]=out[i]=0;
            fa[i]=i;
        //  rank[i]=0;
            ex[i]=false;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%s",word);
            int w1=word[0]-'a';
            int w2=word[strlen(word)-1]-'a';
            in[w1]++;
            out[w2]++;
            ex[w1]=ex[w2]=true;
            Union(w1,w2);
        }
        int ans=0;
        for(int i=0;i<26;i++)
        {
            if(ex[i]&&i==fa[i])
            ans++;
            if(ans>1)
            break;
        }
        if(ans>1)
        {
            printf("The door cannot be opened.\n");
            continue;
        }
        int flag=0;
        int s1=0,s2=0;
        for(int i=0;i<26;i++)
        {
            if(ex[i]&&in[i]!=out[i])
            {
                if(in[i]==out[i]+1)
                s1++;
                else if(in[i]+1==out[i])
                s2++;
                else
                {
                    flag=1;
                    break;
                }
            }
        }
        if(flag)
        {
            printf("The door cannot be opened.\n");
        }else
        {
            if(s1<=1&&s2<=1)
            printf("Ordering is possible.\n");
            else
            printf("The door cannot be opened.\n");
        }
    }
    return 0;
}