拓扑排序&欧拉路专题

集训队

A - 确定比赛名次 HDU - 1285

简单的拓扑排序，需要注意的是这里对于多种排序结果，输出字典序小的那种，这里用优先队列解决此问题，优先队列+拓扑

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
const int maxn=505;
using namespace std;
vector<int>G[maxn];
vector<int>ans;
//queue<int>q;
priority_queue<int,vector<int>,greater<int>>q;   
int n,deg[maxn],m;
void bfstop()
{
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int p=q.top();
        q.pop();
        ans.push_back(p);
        for(int j=0;j<G[p].size();j++)
        {
            --deg[G[p][j]];
            if(deg[G[p][j]]==0)
                q.push(G[p][j]);
        }
    }
}
int main()
{
    int a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans.clear();
        for(int i=0;i<maxn;i++)
            G[i].clear();
        memset(deg,0,sizeof(deg));
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            G[a].push_back(b);
            ++deg[b];
        }
        bfstop();
        for(int i=0;i<ans.size()-1;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[ans.size()-1]);
    }
    return 0;
}

B - Reward HDU - 2647

老板分配工资，每个人最少888，题中给予每个人工资高低顺序，求老板最少需要分配多少工资，若没有合理方案则输出-1.
我们可以反向建图，每个点值初始化为888，然后拓扑一下，根据贪心原则应该高工资的人和低工资的差距为1老板可以取到最小分配。这里通过判断是否有环来判断是否合理，可以直接判断拓扑排序点的个数与n比较

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
const int maxn = 2e4+5;
using namespace std;
vector<int>G[maxn];
queue<int>hyx;
int cost[maxn],deg[maxn];
int n,m,ans,num;
void init()
{
    memset(deg,0,sizeof(deg));
    memset(cost,0,sizeof(cost));
    for(int i=0;i<maxn;i++) G[i].clear();
    for(int i=0;i<maxn;i++) cost[i]=888;
}
void bfstop()
{
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==0)
            hyx.push(i);
    }
    while(!hyx.empty())
    {
        int p=hyx.front();
        ans+=cost[p];
        num++;
        hyx.pop();
        for(int i=0;i<G[p].size();i++)
        {
            --deg[G[p][i]];
            if(deg[G[p][i]]==0)
            {
                cost[G[p][i]]=cost[p]+1;
                hyx.push(G[p][i]);
            }
        }
    }
}
int main()
{
    int a,b;
    while(cin>>n>>m)
    {
        init();
        ans=0;
        num=0;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            G[b].push_back(a);
            deg[a]++;
        }
        bfstop();
        if(num!=n) cout<<"-1"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

D - 欧拉回路 HDU - 1878

裸的判断是否存在欧拉回路模板，回路的话没有奇数个数的点，欧拉路的话至多2个奇数的点，作为起点和终点。这里无向图，记录每个点的度数，并查集再判断图是否连通，满足欧拉路。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int maxn=5e4+5;
using namespace std;
int deg[maxn],par[maxn];
int n,m;
int find(int x)
{
    if(x==par[x])
        return x;
    else
        return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
        par[x]=y;
}
void init(){
    for(int i=1;i<=n;++i)
        par[i]=i;
    memset(deg,0,sizeof(deg));
}
int main()
{
    while(cin>>n>>m)
    {
            int a,b,cnt=0,gen=0;
    init();
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        if(a==b) continue;
        else
        {
            deg[a]++;
            deg[b]++;
            unite(a,b);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(deg[i]&1)
            cnt++;
        if(par[i]==i)
            gen++;
    }
    if(cnt==0&&gen==1)
        printf("1\n");
    else
        printf("0\n");
    }
    return 0;
}