• 图论（欧拉路径）

    理论：

    所有边都经过一次，若欧拉路径，起点终点相同，欧拉回路
    有向图欧拉路径：恰好一个out=in+1,一个in=out+1,其余in=out
    有向图欧拉回路：所有in=out
    无向图欧拉路径：两个点度数奇，其余偶
    无向图欧拉回路：全偶

    基础练习

    P7771 【模板】欧拉路径
    P2731 [USACO3.3] 骑马修栅栏 Riding the Fences
    P1341 无序字母对

    进阶

    P3520 [POI2011] SMI-Garbage
    题意：n点m条边以及边的目前状态目标状态，若干辆垃圾车跑欧拉回路，每次垃圾车经过改变路的状态
    给出需要跑多少次欧拉回路和每次欧拉回路的路径才能所有边实现目标
    思路：无向图欧拉回路拆环,
    欧拉回路边只经过一次，于是当前状态与目标状态相同的边不用管
    变成ol回路拆环问题，考虑在入栈的时候检查该元素是否在栈中,若在,表示成环。
    由于常见的求欧拉路的程序给出的结尾都不是开头点,所以在dfs调用后栈里面还剩下一个环,输出即可。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    13. #define ms(x,y) memset(x,y,sizeof x);
    14. #define YES cout<<"YES"<<'\n';
    15. #define NO  cout<<"NO"<<'\n';
    16. #define fr(i,z,n) for(int i = z;i <= n; i++)
    17. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    18. #define fer(i,x)   for(int i=e.head[x];~i;i=e.next[i])
    19. typedef long long ll;
    20. const ll N= 1e6  + 10, inf = 1e18;
    21. const ll mod = 1e9 + 7;
    22. using namespace std;
    23.  
    24. int n, m;
    25. int vist[N];            //标记点
    26. int vis[N<<1];                     //标记边
    27. int deg[N],instack[N];
    28. int tot;
    29. stack<int>sta;
    30. vector<int>va[N];
    31. template<size_t size>
    32. struct Road {
    33. 	int to[size<<1], next[size<<1], head[size<<1], cnt = 1;
    34. 	ll w[size<<1];
    35. 	void add(int x, int y, ll ww) {
    36. 		to[cnt] = y;
    37. 		w[cnt] = ww;
    38. 		next[cnt] = head[x];
    39. 		head[x] = cnt++;
    40. 	}
    41. 	void clear(int n) {
    42. 		for (int i = 0; i <= n; i++) {
    43. 			head[i] = -1;
    44. 		}
    45. 		cnt = 0;
    46. 	}
    47. 	
    48. };
    49. Road  e; // 无向图 * 2
    50. void dfs(int x) {
    51. 	vist[x] = 1;
    52. 	fer(i, x) {
    53. 		int v = e.to[i];
    54. 		if (!vis[i]) {        //边未标记，每条无向边只能走一次
    55. 			vis[i] = vis[i ^ 1] = 1;             //两条有向边组成无向边
    56. 			e.head[x] = e.next[i];       //下一次直接从nex[i]开始,降低时间复杂度
    57. 			dfs(v);
    58. 			if (instack[v]) {    
    59. 				va[tot].push_back(v);
    60. 				while (sta.top()!=v) {
    61. 					va[tot].push_back(sta.top());
    62. 					instack[sta.top()] = 0;
    63. 					sta.pop();
    64. 				}
    65. 				va[tot].push_back(v);
    66. 				tot++;
    67. 			}
    68. 			else {
    69. 				sta.push(v);
    70. 				//cout << v << '\n';
    71. 				instack[v] = 1;
    72. 			}
    73. 		}
    74. 	}
    75. }
    76. void solve() {
    77. 	scanf("%d %d", &n, &m);
    78. 	e.clear(n);
    79. 	fr(i, 1, m) {
    80. 		int x, y, f, t;
    81. 		scanf("%d %d %d %d", &x, &y, &f, &t);
    82. 		if (f ^ t) {      //相异，需要经过     
    83. 			e.add(x, y, 0);
    84. 			e.add(y, x, 0);
    85. 			deg[x]++;
    86. 			deg[y]++;
    87. 		}
    88. 	}
    89. 	int flag = 0;
    90. 	fr(i, 1, n) {
    91. 		if (deg[i] % 2) {           //无向图的欧拉回路应该为全偶
    92. 			flag = 1;
    93. 			break;
    94. 		}
    95. 	}
    96. 	if (flag) {
    97. 		printf("NIE\n");
    98. 		return;
    99. 	}
    100. 	fr(i, 1, n) {
    101. 		if (!vist[i]) {               //点未标记
    102. 			dfs(i);
    103. 			if (instack[i]) {    //多个环以i为起点，剩余最后一个环
    104. 				va[tot].push_back(i);
    105. 				while (!sta.empty()) {
    106. 					va[tot].push_back(sta.top());
    107. 					instack[sta.top()] = 0;
    108. 					sta.pop();
    109. 				}
    110. 				tot++;
    111. 			}
    112. 		}
    113. 	}
    114. 	printf("%d\n", tot);
    115. 	for (int i = 0; i < tot; i++) {
    116. 		printf("%d ", va[i].size()-1);
    117. 		for (auto it : va[i]) {
    118. 			printf("%d ", it);
    119. 		}
    120. 		printf("\n");
    121. 	}
    122. }
    123.  
    124. signed main()
    125. {
    126. 	ios;
    127. 	int t = 1;
    128. 	//cin >> t;
    129. 	while (t--) {
    130. 		solve();
    131. 	}
    132. }

    P3443 [POI2006] LIS-The Postman
    题意:给定一个有向图，规定路线从1开始1结束，经过每条边恰好一次，同时给定一些序列
    序列在路线中需要连续出现，求满足的路线
    x,y<=n<=5e4,m<=2e5
    思路：难点在于序列的合并
    序列顺序要有边，同时序列的前驱和后继只能有一个，用E存边
     用pre,Next记录序列点的前驱后继在E的位置
    重新建图(将序列合并)，跑欧拉回路，stack入栈起点在在E的位置
    最后还要确定每条边都用上

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    13. #define ms(x,y) memset(x,y,sizeof x);
    14. #define YES cout<<"YES"<<'\n';
    15. #define NO  cout<<"NO"<<'\n';
    16. #define fr(i,z,n) for(int i = z;i <= n; i++)
    17. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    18. #define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])
    19. typedef long long ll;
    20. const ll N = 1e6 + 10, inf = 1e18;
    21. const ll mod = 1e9 + 7;
    22. using namespace std;
    23.  
    24. int in[N];
    25. template<size_t size>
    26. struct Road {
    27.     int to[size], next[size], head[size], cnt = 1;
    28.     ll w[size];
    29.     void add(int x, int y, ll ww) {
    30.         to[cnt] = y;
    31.  
    32.         w[cnt] = ww;
    33.         next[cnt] = head[x];
    34.         head[x] = cnt++;
    35.     }
    36.     void clear(int n) {
    37.         for (int i = 0; i <= n; i++) {
    38.             head[i] = 0;
    39.         }
    40.         cnt = 1;
    41.     }
    42. };
    43. Roade;
    44. int n, m;
    45. map<int, int>H[N];
    46. pair<int, int>E[N];
    47. int pre[N], Next[N], b[N],vis[N];
    48. stack<int>sta;
    49. bool ans = 0;
    50. void dfs(int x) {
    51.     fer(i, x) {
    52.         int v = e.to[i];
    53.         if (!vis[i]) {
    54.             vis[i] = 1;
    55.             e.head[x] = e.next[i];
    56.             dfs(v);
    57.             sta.push(e.w[i]);           //入栈起点在E的位置
    58.         }
    59.     }
    60. }
    61. void solve() {
    62.     cin >> n >> m;
    63.     fr(i, 1, m) {
    64.         int x, y;
    65.         cin >> x >> y;
    66.         E[i] = make_pair(x, y);     //记录边
    67.         H[x][y] = i;    //记录边在E位置      
    68.         in[y]++;
    69.         in[x]--;
    70.     }
    71.     fr(i, 1, n) {
    72.         if (in[i]) {        //有向图的欧拉路径in==out
    73.             ans = 1;
    74.         }
    75.     }
    76.     int k;
    77.     cin >> k;
    78.     fr(i, 1, k) {             
    79.         int cnt,last;
    80.         cin >> cnt;
    81.         cin >> last;
    82.         for (int j = 1; j < cnt; j++) {
    83.             int y;
    84.             cin >> y;
    85.             if (H[last].find(y) == H[last].end()) {    //没有last->y的边
    86.                 ans = 1;
    87.             }
    88.             b[j] = H[last][y];
    89.             last = y;
    90.         }
    91.         for (int j = 2; j < cnt;j++) {    //处理前驱后继以及边的合并
    92.             if (!pre[b[j]]) {
    93.                 pre[b[j]] = b[j - 1];
    94.             }
    95.             else if (pre[b[j]] != b[j - 1]) {    //因为每条边只能出现一次
    96.                 ans = 1;
    97.             }
    98.             if (!Next[b[j-1]]) {
    99.                 Next[b[j - 1]] = b[j];
    100.             }
    101.             else if(Next[b[j-1]]!=b[j]) {
    102.                 ans = 1;
    103.             }
    104.         }
    105.      }
    106.     if (ans == 1) {
    107.         cout << "NIE" << '\n';
    108.         return;
    109.     }
    110.     int c = 0;
    111.     fr(i, 1, m) {                  //建图
    112.        if (!pre[i]) {
    113.            ++c;
    114.            int j;
    115.            for (j = i; Next[j]; j = Next[j]) c++;
    116.            e.add(E[i].first, E[j].second, i);        //i记录起点在E的位置
    117.        }
    118.     }
    119.     if (c < m || !e.head[1]) {     //判断联通(c==m)和能否从1开始
    120.         cout << "NIE" << '\n';
    121.         return;
    122.     }
    123.     fr(i, 1, n) {             //建图后需要再判断
    124.         if (in[i]) {
    125.             cout << "NIE" << '\n';
    126.             return;
    127.         }
    128.     }
    129.     dfs(1);           //欧拉回路
    130.  
    131.     fr(i, 1, n) {                           
    132.         if (e.head[i]) {                 //确定每条边都用上
    133.             cout << "NIE" << '\n';
    134.             return;
    135.         }
    136.     }
    137.  
    138.     cout << "TAK" << '\n';
    139.     cout << 1 <<'\n';
    140.     while (!sta.empty()) {
    141.         int j = sta.top();
    142.         sta.pop();
    143.         while (j) {
    144.             cout << E[j].second << '\n';
    145.             j = Next[j];
    146.         }
    147.     }
    148. }
    149.  
    150. signed main()
    151. {
    152.     ios;
    153.     int t = 1;
    154.     //cin >> t;
    155.     while (t--) {
    156.         solve();
    157.     }
    158. }

  • 相关阅读:
    Spring @Profile注解使用和源码解析
    【shell】read -t -n1
    MATLAB算法实战应用案例精讲-【图像处理】SLAM技术详解（补充篇）
    什么是Docker和Docker-Compose?
    Tomcat下载安装以及配置（详细教程）
    从单体迁移至微服务，需要有足够的理由和勇气
    【Linux】进程间通信介绍及匿名管道使用
    Python图像处理：局部直方图均衡化和自动色彩均衡化
    Vue3.x Composition API - ToDoList 案例
    做过启动盘的U盘怎么复原？三种方法教你
  • 原文地址：https://blog.csdn.net/m0_75027890/article/details/134236323