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

拓扑排序 欧拉路

题目链接

A - 确定比赛名次

题意

中文题诶，根据比赛结果排名次，A打赢B则A排名比B高，排名不唯一的时候编号最小的排名高

思路

拓扑排序的最基本应用

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 507;

struct cmp{
    bool operator()(const int a, const int b) const{
        return a > b;
    }
};

set<int> v[N];
int d[N];
priority_queue<int,vector<int>,cmp > que; 



void cc(){
    for(int i = 0 ; i < N ; i++)    v[i].clear() , d[i] = 0;
    while( !que.empty() )   que.pop();
}

void toposort(int n){
    bool first = true;
    for(int i = 1 ; i <= n ; i++){
        if( d[i] == 0 ){
            que.push(i);
        }
    }
    while( !que.empty() ){
        int u = que.top();que.pop();
        if( first ) printf("%d",u) , first = false;
        else printf(" %d",u);
        for( auto it = v[u].begin() ; it != v[u].end() ; it++ ){
            d[*it]--;
            if( d[*it] == 0 ){
                que.push(*it);
            }
        }
    }   
    printf("\n");
}

int main(){
    int n,m,a,b;
    while( scanf("%d%d",&n,&m) != EOF ){
        cc();
        while( m-- ){
            scanf("%d%d",&a,&b);
            if( v[a].count(b) == 0 )    v[a].insert(b) , d[b]++;
        }   
        toposort(n);
    }
    return 0;
}

B - Reward

题意

老板给公司员工发工资，为了表彰工作好的员工，工作好的员工的工资会高于工资略差的员工至少一元，每个员工工资保底888元，现在给你那些员工做得比那些员工好，让你求出最少的工资总量，如果无法给出，输出-1

思路

拓扑排序的时候用优先队列来维护每一层，每一层都记录处理开始时的队列大小m，之后每层处理都只出队m次，第一层+0元，第二层+1元，依次类推，最后在+888*n元即为最后答案

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4+7;

set<int> v[N];
int d[N] , as[N] , ans;
queue<int> que; 
bool f[N];


void cc(){
    for(int i = 0 ; i < N ; i++)    v[i].clear() , d[i] = 0 , as[i] = -1 , f[i] = false;
    while( !que.empty() )   que.pop();
    ans = 0;
}

void toposort(int n){
    for(int i = 1 ; i <= n ; i++){
        if( d[i] == 0 ) que.push(i) , d[i]--;
    }       
    if( que.empty() ){
        ans = -1;
        return;
    }
    int now = 0 , quesize; 
    while( !que.empty() ){
        quesize = que.size();
        while( quesize--  ){
            int u = que.front();que.pop();
            f[u] = true;
            as[u] = now;
            for( auto it = v[u].begin() ; it != v[u].end() ; it++ ){
                d[*it]--;
                if( d[*it] == 0 )   que.push(*it);
            }
        }
        now++;
    }
    for(int i = 1 ; i <= n ; i++)
        if( as[i] != -1 )   ans += as[i];
        else{
            ans = -1;
            return;
        }
    ans += 888*n;
}

int main(){
    int n,m,a,b;
    while( scanf("%d%d",&n,&m) != EOF ){
        cc();
        while(m--){
            scanf("%d%d",&a,&b);
            if(v[b].count(a) == 0 )  v[b].insert(a) , d[a]++;
        }   
        toposort(n);
        printf("%d\n",ans);
    }
    return 0;
}

C - Rank of Tetris

题意

中文题
Lete制作一个榜单，榜单上每个人都有一个编号和Rating的信息
其中Rating信息只有A > B , A = B , A < B三种情况，优先排序Rating，Rating相同者按编号大小排序
现在问你这些信息能不能构成一个榜单
如果可以输出ok，
否则如果是信息不完全或者自我矛盾按照题意输出

思路

并查集+拓扑排序
将所有Rating相同的点合并成一个集合处理Rating，进行拓扑排序即可

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e4+7;

set<int> v[N];
int d[N] , as[N] , ans , bc[N];
queue<int> que; 
bool f[N];
int data[N][2];
char s[N];

int find(int x){
    if( bc[x] == x )    return x;
    return bc[x] = find(bc[x]);
}

bool bcj(int x){
    int a = find(data[x][0]) , b = find(data[x][1]);
    if( a == b )    return false;
    bc[max(a,b)] = min(a,b);
    return true;
}

void cc(int n){
    for(int i = 0 ; i < n ; i++)    v[i].clear() , d[i] = 0 , as[i] = -1 , f[i] = false,bc[i] = i;
    while( !que.empty() )   que.pop();
    ans = n;
}

void toposort(int n){
    bool undefind = false;
    for(int i = 0 ; i < n ; i++)    if( d[i] == 0 && i == find(i) ) que.push(i);

    while( !que.empty() ){
        if( que.size() > 1 )    undefind = true;
        int u = que.front();que.pop();
        ans--;
        for( auto it = v[u].begin() ; it != v[u].end() ; it++ )
            if( --d[*it] == 0 ) que.push(*it);
    }
    //printf("ans = %d\n",ans);
    if( ans  )  printf("CONFLICT\n");
    else if( undefind ) printf("UNCERTAIN\n");
    else printf("OK\n");
}

int main(){
    int n,m;
    while( scanf("%d%d",&n,&m) != EOF ){
        cc(n);
        for(int i = 0 ; i < m ; i++){
            scanf("%d %c %d",data[i] , s+i , data[i]+1);
            //printf("your_input = %d %c %d\n",data[i][0] , s[i],data[i][1]);
            if( s[i] == '='  && bcj(i)) ans--;
        }
        for(int i = 0 ; i < m ; i++){
            if( s[i] == '=' )   continue;
            int a = find(data[i][0]) , b = find(data[i][1]);
            if( s[i] == '>' ){  if( v[a].count(b) == 0 )    v[a].insert(b) , d[b]++; }  
            else{ if( v[b].count(a) == 0 )  v[b].insert(a) , d[a]++; }  
        }
        toposort(n);
    }
    return 0;
}

D - 欧拉回路

题意

一笔画游戏规则，一笔不重复画边把所有的边画完

思路

欧拉回路+并查集

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1007;

bool v[N][N];
int d[N];
bool vis[N];

bool pdj(int n){
    int count = 0;
    for(int i = 1 ; i <= n && count <= 1; i++){
        if( d[i] & 1 )  count++;
    }
    if( count > 1 ) return false;
    return true;
}

bool bfs(int s , int n){
    memset(vis,true,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s] = false;
    while( !q.empty() ){
        int u = q.front();q.pop();
        for(int i = 1 ; i <= n ; i++){
            if( v[u][i] && vis[i] ) vis[i] = false , q.push(i);
        }
    }
    for(int i = 1 ; i <= n ; i++)   if( vis[i] )    return false;
    return true;
}

int main(){
    int n,m,a,b;
    while( scanf("%d",&n) != EOF && n ){
        scanf("%d",&m);
        memset(v,false,sizeof(v));
        memset(d,0,sizeof(d));
        while( m-- )    scanf("%d%d",&a,&b) , v[a][b] = v[b][a] = true , d[a]++,d[b]++;
        if( pdj(n) && bfs(1,n) )    printf("1\n");
        else printf("0\n");
    }
}

E - Play on Words

题意

英文版成语接龙，给你若干个单词，问你给你的所有单词是否能够满足一个排序，使得下一个单词的首字母是上一个单词的最后一个字母

思路

把每个字母作为首字母和作为最后一个字母的次数记录下来，这时候只需要检测所有字母是否满足作为首字母与作为最后一个字母的情况是相等的，特判开始单词的首字母与结尾单词的尾字母出入差一
还需要用并查集判断所有字母是否联通，防止abc cba bzx xzb的两段情况

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+7;
const int M = 30;

char s[1007];
int in[M] , out[N],b[M];
bool vis[M] ;

int find(int x){
    if( x == b[x] ) return x;
    return b[x] = find(b[x]);
}

void bcj(int a, int c){
    vis[a] = true;
    vis[c] = true;
    a = find(a) , c = find(c);
    if( a != c )    b[c] = a;
}

int main(){
    int t,n;
    scanf("%d",&t);
    while( t-- ){
        scanf("%d",&n);
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(vis,false,sizeof(vis));
        for(int i = 0 ; i < M ; i++)    b[i] = i;
        for( int i = 0 ; i < n ; i++ ){
            scanf("%s",s);
            int len =strlen(s) , a = s[0] - 'a', c = s[len - 1 ] - 'a';
            in[a]++;
            out[c]++;       
            bcj(a,c);
        }
        int inmin = 0 , outmax = 0 , root = 0;
        inmin = outmax = root = 0;
        bool can = true;
        can = true;
        for( int i = 0 ; i < M && can ; i++ ){
            if( !vis[i] )   continue;
            if( b[i] == i ){
                if( ++root > 1 )    break;
            }
            if( in[i] == out[i] )   continue;   
            if( in[i] - out[i] == 1 )   inmin++;
            else if( out[i] - in[i] == 1 )  outmax++;
            else    can = false;                
        }
        if( !can || inmin != outmax || inmin > 1  || root > 1)
            printf("The door cannot be opened.\n");
        else    printf("Ordering is possible.\n"); 
    }
    return 0;
}

F - The Best Path

题意

n 个点 m 条无向边的图，找一个欧拉回路使得这个路径所有结点的异或值最大

思路

首先有：如果这个点经过偶数次，与异或0相当
首先要验证图是否联通
然后在每一个入度的一半（向上取整）为奇数时需要异或一次，其他均为与异或0相当
其次讨论其实位置，如果满足一笔画讨论起点位置，如果起点可以任意选择，则需要暴力枚举所有起点，否则答案唯一
其中入度的一半向上取整表示的是需要路过这个点的次数，所以次数为奇数就需要异或，偶数相当于没有异或，而起点终点肯定要多异或一次

AC代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5+7;
const int M = 30;

int p[N] , d[N] , b[N];

int find(int x){
    if( x == b[x] ) return x;
    return b[x] = find(b[x]);
}

void bcj(int a,int c){
    a = find(a);
    c = find(c);
    if( a != c )    b[c] = a;
}

bool pd(int n , int &ans){
    int cnt = find(1);
    for(int i = 1 ; i <= n ; i++)   if( cnt != find(i) )    return false;
    cnt = 0;
    for(int i = 1 ; i <= n ; i++)   if( d[i] % 2 )  cnt++;
    if( cnt == 0 ){
        for(int i = 1 ; i <= n ; i++)   if( (int)((d[i]+1)/2) % 2 ) cnt ^= p[i];
        for(int i = 1 ; i <= n ; i++)   ans = max(ans,cnt^p[i]);
        cnt = 0;
    }else if(cnt == 2){
        for(int i = 1 ; i <= n ; i++)
            if( (int)((d[i]+1)/2) % 2 )
                ans ^= p[i];            
    }
    return cnt == 0 || cnt == 2; 
}

int main(){
    int t,n,m,ans ,a,c;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(d,0,sizeof(d));
        for(int i = 1 ; i <= n ; i++)   scanf("%d",p+i) , b[i] = i;
        ans = 0;
        for(int i = 0 ; i < m ; i++)    scanf("%d%d",&a,&c) , d[a]++ , d[c]++ , bcj(a,c);
        if( pd(n, ans) )
            printf("%d\n",ans);
        else
            printf("Impossible\n");
    }
    return 0;
}