UESTC 图论专题 A-D

A：梦后楼台高锁，酒醒帘幕低垂

题目链接：http://acm.uestc.edu.cn/#/problem/show/1636

解法：首先，考虑到，我们需要找到一条路径，使它的最小边尽量大，最大边尽量小。然后，考虑到m比较小，我们可以去寻找一个m^2或者m^2logm的算法。考虑枚举最小边，那么我们就需要在m或者mlogm的时间内找到尽量小的最大边.回忆最小生成树的kruskal算法，并查集+贪心加边.应用到此题，从枚举的最小边贪心加边，当1和n属于同一个集合时停止，得出的一定是当前最小边情况下的最优解


#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v,w;
}E[1010];
int n,m;
int fa[210],edgecnt;
bool cmp(edge a, edge b){
    return a.w<b.w;
}
int find_set(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find_set(fa[x]);
}
void union_set(int x, int y){
    int fx=find_set(x),fy=find_set(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}
int main()
{
    while(~scanf("%d %d",&n,&m)){
        for(int i=1; i<=n; i++) fa[i]=i;
        for(int i=1; i<=m; i++){
            scanf("%d %d %d", &E[i].u,&E[i].v,&E[i].w);
        }
        sort(E+1,E+m+1,cmp);
        int ans=1e9;
        for(int i=1; i<=m; i++){
            for(int i=1; i<=n; i++) fa[i]=i;
            union_set(E[i].u,E[i].v);
            if(find_set(1)==find_set(n)){
                ans=0;
                break;
            }
            for(int j=i+1; j<=m; j++){
                union_set(E[j].u,E[j].v);
                if(find_set(1)==find_set(n)){
                   ans=min(ans,E[j].w-E[i].w);
                   break;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B：去年春恨却来时，落花人独立，微雨燕双飞

题目链接：http://acm.uestc.edu.cn/#/problem/show/1633

解法：

对于S集合中的数，例如a1，考虑到如果x能够被表示出来，那么x+a1也一定能被表示出来。
故设d[r]为所有模a1余r的数中，能被表示出来的最小的数。
故可以表示出一个a1个节点a1*n条边的有向图。
d[0] = 0,丢入priority_queue<ii, vector<ii>, greater<ii>>，然后对于pq.top()的点连出的n条边进行松弛操作。
如果 d[u] + a[i] < d[(d[u] + a[i])] 则刷新并丢入队列。
跑出来的d[i]，如果d[i] != INF则都是可以表示出来的。
对于每个询问判断 q >= d[q % a[1]]即可。
时间复杂度 O(mlogn)
空间复杂度 O(n)，不用存边。


#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
const int maxm = 50010;
const int inf = 1e9+8;
int a[maxn], dis[maxm];
bool vis[maxm];
int n,m,x;
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > >q;
void Dij()
{
    while(!q.empty()) q.pop();
    for(int i=0; i<maxm; i++) dis[i]=inf,vis[i]=0;
    memset(vis,false,sizeof(vis));
    dis[0]=0;
    q.push(make_pair(0,0));//first->num,second->num%a[1]
    while(!q.empty()){
        int u = q.top().second;
        int d = q.top().first;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=1; i<=n; i++){
            if(d+a[i]<dis[(d+a[i])%a[1]]){
                dis[(d+a[i])%a[1]] = d+a[i];
                q.push(make_pair(d+a[i],(d+a[i])%a[1]));
            }
        }
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        Dij();
        scanf("%d", &m);
        while(m--){
            scanf("%d", &x);
            if(x>=dis[(x%a[1])]){
                puts("YES");
            }
            else{
                puts("NO");
            }
        }
    }
    return 0;
}

C:记得小苹初见，两重心字罗衣
题目链接：http://acm.uestc.edu.cn/#/problem/show/1634

解法：把每个点看成边，每个横纵坐标看成一个点，得到一个无向图.如果新图中每个点的度都是偶数，那么就是一个欧拉图，对该图跑一遍欧拉回路，对走过的边轮流染色，就可以保证每个点所连的边的红蓝颜色相等.如果存在度数为奇数的点，新建两个点a和b.把横坐标的度数为奇数的点和a连边，把纵坐标为奇数的点和b连边，这样最多只有a和b的度数为奇数，可以跑欧拉路径.


#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5+6;
const int maxm = 3*2e5+6;
vector <pii> G[maxn*3];
vector <int> ans;
bool vis[maxm];
int anss[maxm];
int n;
inline void add(int x, int y, int z){
    G[x].push_back(pii(z,y));
    G[y].push_back(pii(z,x));
}
inline void dfs(int u){
    int v, e;
    while(!G[u].empty()){
        v = G[u].back().second, e = G[u].back().first;
        G[u].pop_back();
        if(!vis[e]){
            vis[e] = 1;
            dfs(v);
            ans.push_back(e);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        add(x, y+maxn, i);
    }
    int st = -1, a = 2*maxn+1, b = a+1, cnt = n;
    for(int i=1; i <= 2*maxn; i++){
        int sz = G[i].size();
        if(sz){
            if(sz&1){
                if(i<=maxn){
                    add(a, i, ++cnt);
                    if(st != a) st = a;
                }
                else{
                    add(b, i, ++cnt);
                    if(st != b) st = b;
                }
            }
            if(st == -1) st = i;
        }
    }
    dfs(st);
    for(int i = 1; i <= 2*maxn; i++){
        if(G[i].size()){
            dfs(i);
        }
    }
    int sz = ans.size();
    for(int i = 0; i < sz; i++){
        if(ans[i] <= n){
            anss[ans[i]] = i&1;
        }
    }
    for(int i=1; i <=n ; i++){
        if(anss[i]) putchar('r');
        else putchar('b');
    }
    return 0;
}

D：琵琶弦上说相思，当时明月在，曾照彩云归
题目链接：http://acm.uestc.edu.cn/#/problem/show/1635

解法：

拓扑排序、bfs
对于相邻的2个字符串当第一次遇到不相等的字符是前一个u必定比比后一个v小，
所以可以u向v连一条有向边。
然后对于建出的这个图，跑一次拓扑排序即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int maxn = 1010;
char s[maxn][300];
vector <int> G[30];
queue <int> q1;
priority_queue <pii, vector<pii>, greater<pii> > q2;
int du[30];
bool vis[maxn];
void topsort()
{
    while(!q2.empty()){
        int u = q2.top().first;
        int fa = q2.top().second;
        q2.pop();
        q1.push(u);
        vis[u] = 1;
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            if(v == fa) continue;
            du[v]--;
            if(du[v] == 0){
                q2.push(pii(v, u));
            }
        }
    }
}
int main()
{
    int n, len1, len2;
    scanf("%d", &n);
    bool ans = 1;
    for(int i = 0; i < n; i++) scanf("%s", s[i]);
    for(int i = 0; i < n- 1; i++){
        len1 = strlen(s[i]);
        len2 = strlen(s[i+1]);
        bool flag = 0;
        for(int j = 0; j < min(len1, len2); j++){
            if(s[i][j] !=s[i+1][j]){
                flag = 1;
                G[s[i][j]-'a'].push_back(s[i+1][j]-'a');
                break;
            }
        }
        if(flag == 0){
            if(len1 > len2){
                ans = 0;
                break;
            }
        }
    }
    if(ans == 0){
        puts("-1\n");
    }
    else{
        for(int i = 0; i < 26; i++){
            for(int j = 0; j < G[i].size(); j++){
                du[G[i][j]]++;
            }
        }
        for(int i = 0; i < 26; i++){
            if(G[i].size() && du[i] == 0){
                q2.push(pii(i, -1));
            }
        }
        topsort();
        for(int i = 0; i < 26; i++){
            if(du[i] != 0){
                ans = 0;
                break;
            }
        }
        if(ans == 0){
            puts("-1");
        }
        else{
            int i = 0;
            while(!q1.empty()){
                while(vis[i]) i++;
                while(i < q1.front()){
                    putchar(char('a'+i));
                    i++;
                    while(vis[i]) i++;
                }
                putchar(char('a'+q1.front())); q1.pop();
            }
            while(vis[i]) i++;
            while(i < 26){
                putchar(char('a' + i));
                i++;
            }
            printf("\n");
        }
    }
    return 0;
}