Cover
- Time Limit: 6000/3000 MS (Java/Others)
- Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 1640
- Accepted Submission(s): 349Special Judge
Problem Description
The Wall has down and the King in the north has to send his soldiers to sentinel.
The North can be regard as a undirected graph (not necessary to be connected), one soldier can cover one path. Today there's no so many people still breathing in the north, so the King wants to minimize the number of soldiers he sent to cover each edge exactly once. As a master of his, you should tell him how to arrange soldiers.
Input
There might be multiple test cases, no more than 20. You need to read till the end of input.
In the first line, two integers n and m, representing the number of nodes and edges in the graph.
In the following m lines, each contain two integers, representing two ends of an edge.
There are no parallel edges or self loops.
1≤n,m≤100000
Output
For each test case, the first line contains number of needed routes, p.
For the following p lines, an integer x in the beginning, followed by x integers, representing the list of used edges. Every integer should be a positive or negative integer. Its absolute value represents the number of chosen edge (1~n). If it's positive, it shows that this edge should be passed as the direction as the input, otherwise this edge should be passed in the direction different from the input. Edges should be in correct order.
Sample Input
3 3
1 2
1 3
2 3Sample Output
1
3 1 3 -2Source
2018 Multi-University Training Contest 2
链接
http://acm.hdu.edu.cn/showproblem.php?pid=6311
题意
给定一个无向图（不一定连通），问至少需要多少条欧拉路径路（一笔画，包括回路）才能覆盖所有的边。
题解
对于一个连通块（单个点除外），如果奇度数点个数为 k，那么至少需要max{k/2,1} 条路径。将奇度数的点两两相连边（虚边），然后先从奇度数的点出发，搜索由其出发的欧拉回路。需要将遍历的边和其反向边打标记，并在DFS退栈的时候记录边的编号（前向星的存储是访问后加入的边），若该边是自己添加的虚边，那么说明实际上这次DFS搜索到的是一条欧拉通路，那么结果还需额外+1，所以对所有奇数点DFS过后，得到的结果就是max{k/2,1}。再从未被访问过的偶数顶点出发搜索由其出发的欧拉回路，每一次DFS就是找到了一条回路。
代码
| Status | Accepted |
|---|---|
| Time | 1154ms |
| Memory | 11124kB |
| Length | 2196 |
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100010;
int tot, cnt, n, m;
struct Edge
{
int to, next, id;
bool f;
}edge[maxn<<2]; // NO MLE
bool vis[maxn];
vector <int> V[maxn];
int degree[maxn];
int head[maxn];
void init()
{
cnt = tot = 0;
for (int i = 0; i <= n; ++i)
{
degree[i] = 0;
vis[i] = false;
head[i] = -1;
}
// memset(edge, 0, sizeof(edge)); // MLE
}
void addedge(int u, int v, int id) // 链式前向星存边
{
edge[tot].to = v;
edge[tot].id = id;
edge[tot].next = head[u];
edge[tot].f = false;
head[u] = tot++;
}
void dfs(int u)
{
vis[u] = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
int id = edge[i].id;
if (!edge[i].f)
{
edge[i].f = edge[i^1].f = true; // 标记边和反向边
dfs(v);
if (id) // 实边
V[cnt].push_back(-id); // 退栈过程中记录边的id，为负是因为先访问方向边
else // 遇到虚边，路径加1
cnt++;
}
}
}
void Print()
{
printf("%d\n", cnt);
for (int i = 0; i < cnt; ++i)
{
int len = V[i].size();
printf("%d", len);
for (int j = 0; j < len; j++)
printf(" %d", V[i][j]);
printf("\n");
V[i].clear();
}
}
int main()
{
int u, v;
while (scanf("%d%d", &n, &m) == 2)
{
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v, i);
addedge(v, u, -i);
degree[u]++, degree[v]++;
}
int pos = 0;
for (int i = 1; i <= n; ++i)
{
if (degree[i] & 1) // 度数为奇数的点连边
{
if (pos > 0)
{
addedge(i, pos, 0);
addedge(pos, i, 0);
pos = 0;
}
else
pos = i;
}
}
for (int i = 1; i <= n; ++i) // 度数为奇数
{
if (!vis[i] && (degree[i]&1))
dfs(i);
}
for (int i = 1; i <= n; ++i)
{
if (!vis[i] && degree[i])
{
dfs(i);
cnt++;
}
}
Print();
}
return 0;
}使用memset初始化结构体会MEL，不知道原因。【好像是原来开的已经超了但是实际上没用那么多，但是使用memset后就直接爆了】然后就是对于链式前向星，它每次都是从最后一条边开始访问的，所以我们dfs后，vector是存的-id，边的顺序也是正序输出。
The end.
2018-07-28 星期六