way Traffic(混合图改有向图)

题目大意：给出一张混合图，要求你改变尽量多的双向边，使得改变后的图还是强连通的

解题思路：这题和poj-1515类似，只不过这题是混合题，，大体思路还是差不多的，在dfs的时候记录一下桥和使用的是哪些边即可

struct Edge{int from, to, dir, next, flag;}E[M];int head[N], pre[N], lowlink[N];int tot, dfs_clock, n, m;void dfs(int u, int fa) {pre[u] = lowlink[u] = ++dfs_clock;for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (E[i].flag != -1) continue;if (E[i].dir == 0) continue;E[i].flag = 1;E[i^1].flag = 0;if (!pre[v]) {dfs(v, u);lowlink[u] = min(lowlink[u], lowlink[v]);if (lowlink[v] > pre[u]) {E[i ^ 1].flag = 1;}}else if (v != fa) {lowlink[u] = min(lowlink[u], pre[v]);}}}void solve() {memset(pre, 0, sizeof(pre));dfs_clock = 0;for (int i = 1; i <= n; i++)if (!pre[i])dfs(i, -1);for (int i = 0; i < tot; i += 2) {if (E[i].dir == 2 && E[i].flag == 1 && E[i^1].flag == 1) {printf(“%d %d 2\n”, E[i].from, E[i].to);}else if (E[i].dir == 2 && E[i].flag == 1 && E[i^1].flag == 0) {printf(“%d %d 1\n”, E[i].from, E[i].to);}else if (E[i].dir == 2 && E[i].flag == 0 && E[i ^ 1].flag == 1) {printf(“%d %d 1\n”, E[i^1].from, E[i^1].to);}}}void AddEdge(int u, int v, int dir) {E[tot].from = u;E[tot].to = v;E[tot].dir = dir;E[tot].flag = -1;E[tot].next = head[u];head[u] = tot++;}void init() {memset(head, -1, sizeof(head));tot = 0;int a, b, c;for (int i = 0; i < m; i++) {scanf(“, &a, &b, &c);if (c == 2) {AddEdge(a, b, c);AddEdge(b, a, c);}else {AddEdge(a, b, c);AddEdge(a, b, 0);}}}int main() {while (scanf(“%d%d”, &n, &m) != EOF) {init();solve();}return 0;}

你可能付出一定的代价，但日后你得到的，远比付出的多得多。