分类目录归档:算法

洛谷 P1144 最短路计数

自己一开始写了个,才60分,效率不高,后来看了题解。
参考题解:https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
            }
        }
    }
}
void DFS(int node,int dist){
    if(dist!=dis[node])return;
    cnter[node]++;
    cnter[node]%=MOD;
    for(int e=fst[node];e!=-1;e=nxt[e]){
        if(visited[e])continue;
        visited[e]=true;
        DFS(v[e],dist+1);
        visited[e]=false;
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    memset(visited,false,sizeof(visited));
    DFS(1,0);
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

100分的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    cnter[1]=1;
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }else if(dis[v[e]]==dis[node]+1){
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }
        }
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

洛谷 P1346 电车

基本上是裸的最短路,是第一个不用扳道岔的边长就是0,后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
    int v,w;
    edge(int vv,int ww){v=vv;w=ww;}
    bool operator < (const edge& e2) const{
        return w>e2.w;
    }
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int v;
            cin>>v;
            if(j==1)edges[i].push_back(edge(v,0));
            else edges[i].push_back(edge(v,1));
        }
    }
    //Dijkstra
    memset(dis,0x7f,sizeof(dis));
    pq.push(edge(a,0));
    while(!pq.empty()){
        edge cur=pq.top();
        pq.pop();
        if(visited[cur.v])continue;
        visited[cur.v]=true;
        dis[cur.v]=cur.w;
        for(int i=0;i<edges[cur.v].size();i++){
            if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
                dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
                pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
            }
        }
    }
    if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
    else cout<<-1;
}

洛谷 P1288 取数游戏II

博弈论……不会……直接看题解……
https://www.luogu.org/blog/user18431/solution-p1288
https://www.luogu.org/blog/fusu2333/solution-p1288

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, arr[22];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = 1; i <= n; i++)if (arr[i] == 0) {
        if (i % 2 == 0) {
            cout << "YES";
            return 0;
        }
        break;
    }
    for (int i = n; i >= 1; i--)if (arr[i] == 0) {
        if ((n - i + 1) % 2 == 0) {
            cout << "YES";
            return 0;
        }
        break;
    }
    cout << "NO";
}

洛谷 P1247 取火柴游戏

新技能点:博弈论:内容:Nim游戏
参考链接:https://blog.csdn.net/summer__show_/article/details/70185470
https://baike.baidu.com/item/Nim%E6%B8%B8%E6%88%8F/6737105?fr=aladdin
https://blog.csdn.net/kamisama123/article/details/77649118

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int k;
int arr[500005];
int main() {
    ios::sync_with_stdio(false);
    cin >> k;
    for (int i = 1; i <= k; i++)cin >> arr[i];
    int re = arr[1];
    for (int i = 2; i <= k; i++)re ^= arr[i];
    if (re == 0) {
        cout << "lose";
        return 0;
    }
    for (int i = 1; i <= k; i++) {
        if ((re^arr[i]) < arr[i]) {
            cout << arr[i] - (re ^ arr[i]) << " " << i << endl;
            arr[i] ^= re;
            for (int i = 1; i <= k; i++)cout << arr[i] << " ";
            break;
        }
    }
}

洛谷 P1991 无线通讯网

这道题很显然能够看出,只需找出与卫星电话数相等的联通块数,然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后,经题解提醒“树的性质:删掉n条边一定出现n+1个连通块”,这样就好做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int s, p;
struct edge {
    int u, v;
    double w;
    bool operator < (const edge& e2) const {
        return w < e2.w;
    }
}edges[125000];
struct point {
    int x, y;
}points[505];
int father[505];
int _find(int x) {
    if (father[x] == 0)return x;
    return father[x] = _find(father[x]);
}
bool _union(int x, int y) {
    x = _find(x); y = _find(y);
    if (x == y)return false;
    father[x] = y;
    return true;
}
inline double dis(int x1, int y1, int x2, int y2) {
    return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> points[i].x >> points[i].y;
    }
    int ePtr = 0;
    for (int i = 1; i <= p; i++) {
        for (int j = i + 1; j <= p; j++) {
            ePtr++;
            edges[ePtr].u = i;
            edges[ePtr].v = j;
            edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y);
        }
    }
    sort(edges + 1, edges + ePtr + 1);
    int cnter = 0;
    for (int i = 1; i <= ePtr; i++) {
        if (_union(edges[i].u, edges[i].v)) {
            cnter++;
        }
        if (cnter == p - 1 - (s - 1)) {
            printf("%.2lf", edges[i].w);
            break;
        }
    }
}

洛谷 P1414 又是毕业季II

不是特别会做,看了题解,好像还挺简单了,写代码写了挺长时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int score[10005];
int cnts[1000005];
int cnts2[10005];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cnts[1] = n;
    for (int i = 1; i <= n; i++)cin >> score[i];
    int maxV = 0;
    for (int i = 1; i <= n; i++) {
        if (score[i] != 1)cnts[score[i]]++;
        maxV = max(maxV, score[i]);
        for (int j = 2; j <= sqrt((double)score[i]); j++) {
            if (score[i] % j == 0) {
                cnts[j]++;
                if (j*j != score[i])cnts[score[i] / j]++;
            }
        }
    }
    for (int i = 1; i <= maxV; i++) {
        if(cnts[i]!=0)cnts2[cnts[i]] = i;
    }
    for (int i = n; i > 0; i--)cnts2[i] = max(cnts2[i], cnts2[i + 1]);
    for (int i = 1; i <= n; i++)cout << cnts2[i] << endl;
}

数论代码总结

欧几里得:求a,b的最大公约数。

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

扩展欧几里得:(求a,b的最大公约数和不定方程ax+by=d(=gcd(a,b))的一对解)
裴蜀定理
对于任意整数 a , b,存在无穷多组整数对 (x,y) 满足不定方程 ax+by=d ,其中 d=gcd(a,b)
在求 d=gcd(a,b)的同时,可以求出关于x,y的不定方程ax+by=d的一组整数解。
考虑递归计算:假设已经算出了(b,a \bmod b)的一对解(x_0,y_0)满足bx_0+(a \bmod b)y_0=d
可以得到bx_0+(a – b \left \lfloor \frac{a}{b} \right \rfloor)y_0=d
整理可得b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0) +ay_0=d
ay_0+b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0)=d
x=y_0,y=x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0
假设先行swap(x_0,y_0),则有x=x_0,y=y_0-\left \lfloor \frac{a}{b} \right \rfloor x_0

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

乘法逆元
方法1:利用扩展欧几里得求逆元,参见:https://renjikai.com/luogu-p1082/
适用条件:被求数a和模数b互质。
方法2:利用费马小定理(快速幂)求逆元,参见:https://renjikai.com/luogu-p1313/
适用条件:模数为质数。(保证了被求数a和模数b互质。)
方法3:不用记复杂的线性递推公式,就可以用O(N)复杂度推出1到n的所有乘法逆元(模意义下,在后面不再赘述)。除此之外,在此过程中求出1!n!的阶乘及其逆元。
前提结论:易知\prod_{i=1}^{n}\ inv(i)=inv(n!)
乘法逆元定义:inv(i)\cdot i\equiv 1
令数组A_i=i!,容易求出数组A。令数组B_i=inv(i!),那么数组B应该怎么求呢?
用方法1、2容易求出inv(A_n),即inv(n!),即求出了B_n
由前提结论知,B数组的递推公式为B_i=B_{i-1} \cdot inv(i),两边同乘i,则有B_i \cdot i =B_{i-1} \cdot inv(i)\cdot i,由乘法逆元定义有B_{i-1} = B_i \cdot i,只需回推,即可求出由i!的乘法逆元。
B_n=\prod_{i=1}^{n} inv(i)=inv(n)\cdot inv(n-1) \cdot inv(n-2) … \cdot inv(1)A_{n-1}=(n-1)!=(n-1)\cdot(n-2)…\cdot(1),因此两式相乘则有inv(n)=B_{n\cdot A}{n-1},即求出了1到n的所有乘法逆元,是线性复杂度O(N),可能常数大一点,但是好记啊。
C++伪代码如下:(不一定完全正确,请注意识别)

#define MOD
#define ll long long

ll quickpow(ll a, ll b);
ll fInv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
ll n;
ll fact[n + 2];
ll invFact[n + 2];
ll inv[n + 2];
void gen() {
    fact[1] = 1;
    for (ll i = 2; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[n] = fInv(fact[n]);
    for (ll i = n - 1; i >= 1; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
    inv[1] = 1;
    for (ll i = 2; i <= n; i++) {
        inv[i] = invFact[i] * fact[i - 1] % MOD;
    }
}

洛谷 P4779 【模板】单源最短路径(标准版)

SPFA 40;Dijkstra AC.
这个Dijkstra是没问题的版本,有问题的参见:https://renjikai.com/luogu-p1339/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts;
struct edge {
    long long v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
    bool operator < (const edge& e2) const{
        return w > e2.w;
    }
};
vector<edge> edges[100005];
long long dis[100005];
bool inqueue[100005];
bool visited[100005];
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
void dijkstra() {
    priority_queue<edge> pq;
        dis[ts] = 0;
    pq.push(edge(ts,0));
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (visited[e.v])continue;
        visited[e.v] = true;
        //dis[e.v] = e.w;
        for (int i = 0; i < edges[e.v].size(); i++) {
            if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入
                dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w;
                pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    //SPFA();
    dijkstra();
    for(int i=1;i<=t;i++)cout << dis[i]<<" ";
}

20190524更新,又写了一次Dijkstra ^v^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include<iomanip>
using namespace std;
int n, m, s;
struct edge {
    int g, w;
    edge(int g, int w) :g(g), w(w) {}
    bool operator < (const edge& e1) const{
        return this->w > e1.w;
    }
};
vector<edge> edges[100005];
int dis[100005];
bool visited[100005];
void dijkstra() {
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<edge> pq;
    pq.push(edge(s, 0));
    while (!pq.empty()) {
        edge node = pq.top();
        pq.pop();
        if (visited[node.g])continue;
        visited[node.g] = true;
        if (node.w >= dis[node.g])continue;
        dis[node.g] = node.w;
        for (int i = 0; i < edges[node.g].size(); i++) {
            edge & curE = edges[node.g][i];
            if(!visited[curE.g])pq.push(edge(curE.g, node.w + curE.w));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int f, g, w;
        cin >> f >> g >> w;
        edges[f].push_back(edge(g, w));
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x7f7f7f7f)cout << "2147483647 ";
        else cout << dis[i] << " ";
    }
}

洛谷 P1339 [USACO09OCT]热浪Heat Wave

头一次用dijkstra写题也是想试验一下,priority_queue的小根堆用的不熟。。让人不知所以。。。
应该有个这样的小窍门。pq的默认是搞大根堆的,直接想非常不好想,写排序规则的地方只写<号,然后写成“假设你就要把大数排在前面,即顺着pq排序规则走的规则,然后把符号一反即可”。 两种方法代码里都有: 注意!该题中的Dijkstra算法错误,请勿继续使用!错误问题在堆判断dis时不能做到实时动态更新,而将dis插入到堆排序的结构体中可以使得堆中重复插入点相同,路径值不同的结构体值,这样点同路径值小的可以传到堆顶,大的在到顶时被忽略。
没问题的版本参见:https://renjikai.com/luogu-p4779/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts, te;
struct edge {
    int v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
};
vector<edge> edges[2505];
int dis[2505];
bool inqueue[2505];
//bool visited[2505];
/*
struct cmp {
    bool operator () (int i1, int i2) {
        return dis[i1] > dis[i2];
    }
};
*/

void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
/*
void dijkstra() {
    priority_queue<int,vector<int>,cmp> pq;
    dis[ts] = 0;
    pq.push(ts);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        if (visited[node])continue;
        visited[node] = true;
        for (int i = 0; i < edges[node].size(); i++) {
            if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入,这也是为什么cmp必须要用实时的数据
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                pq.push(edges[node][i].v);
            }
        }
    }
}
*/

int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts >> te;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
        edges[re].push_back(edge(rs, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    SPFA();
    //dijkstra();
    cout << dis[te];
}

洛谷 P1341 无序字母对

本题涉及欧拉回路/欧拉路径。
参考:https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
struct e {
    char t;
    int bool_v;
    e(char t1, int v1) { t = t1; bool_v = v1; }
    bool operator < (const e& e2) const {
        return t < e2.t;
    }
};
vector<e> edge[130];
vector<char> path;
int degree[130];
bool visited[3000];
void dfs(char node) {
    for (int i = 0; i < edge[node].size(); i++) {
        if (visited[edge[node][i].bool_v])continue;
        visited[edge[node][i].bool_v] = true;
        dfs(edge[node][i].t);
    }
    path.push_back(node);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        degree[c1]++;
        degree[c2]++;
        edge[c1].push_back(e(c2, i));
        edge[c2].push_back(e(c1, i));
    }
    for (char i = 0; i <= 126; i++) {
        if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end());
    }
    int odd = 0;//奇
    char s = -1;
    for (char i = 127; i >= 0; i--) {
        if (degree[i] % 2 == 0 && degree[i] > 0) {
            if (odd == 0)s = i;
        }
        else if (degree[i] % 2 == 1) {
            odd++;
            s = i;
        }
    }
    if (!(odd == 0 || odd == 2)) {
        cout << "No Solution";
        return 0;
    }
    dfs(s);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
    }
}

可能确实不大好理解这个代码,然后就做了一个简易的例子来说明这个问题。