Electricity
Time Limit: 10 Seconds Memory Limit: 32768 KB Special Judge
After recent blackouts in some regions in North America, the government has decided to reorganize the power supply network of the continent.
The power supply network is the set of nodes, such as power plants or transformation stations, connected by transmission lines. All lines are used to transmit electricity from one node to another. For stability reasons the system is organized in such a way that there are no directed cycles.
Since the government is currently short of money due to several small peaceful militaristic operations, it cannot build new power lines for the moment. So after reorganization the same lines will be used, but some lines will have to transmit electricity in the direction opposite to the current one. To make the reorganization gentle enough, the management of the power network is planning to switch the transmission direction for exactly one line each day. Of course, no day there must be a cycle in a network, since this may cause damage to the system. The resulting network is also designed to be acyclic.
Help them to plan the reorganization.
Input
There are mutilple cases in the input file.
The first line of the input file contains n --- the number of nodes in the network, and m --- the number of transmission lines (2 <= n <= 1,000 , 1 <= m <= 10,000 ). The following m lines contain three integer numbers each. The first two give the source and the destination node for the corresponding line in the current node. The third number is 0 if the line must keep its transmission direction in the resulting network, and 1 if the direction must be reversed.
There can be several lines connecting the same pair of nodes, but due to acyclicity condition, they all transmit electricity in the same direction. This is also the reason why no line connects a node to itself.
There is an empty line after each case.
Output
First output k --- the number of days in the plan you suggest. You don't need to minimize this number, but it must not exceed 4m . After that print k integer numbers --- for each day output the number of the line that changes the transmission direction this day. If it is impossible to make the desired reorganization, output -1 instead of k .
There should be an empty line after each case.
Sample Input
4 5
1 2 0
2 3 1
2 4 1
1 4 1
4 3 0
2 2
1 2 1
1 2 1
Sample Output
3
3 2 4
-1
Source: Andrew Stankevich's Contest #9
一道不错的图论题，大意是给一个有向网络N，必须将其中X条边反向，给出一个方案顺序，使得在执行反向的过程中，网络不会出现环，如果不存在这个方案，输出-1.
思路：首先，判断不存在的情况：1.两个重边都要反转，那么在操作过程中肯定出现环；2.在初始网络或结束网络存在环。对于第二种情况，可以用topo排序求一下两个网络是否存在环，并记录下topp序列。
之后，我们要构造方案，构造方案的过程有两个：
1.一个点的可逆入度边（这句是废话，可逆边就是必须改变的边，肯定包含于方案，但注意是入度）
2.这个点必须从结尾网络的topo序列从后往前搜索.....（凌乱了吧....）
首先，我们要明白topo序列的性质，就是序列a1,a2,a3,...,an，表示的是网络n个点的线性关系，存在任意的i<j,使得ai -> aj，也就是，如果用网络表示topo序列，那么只有往右边指向的边。
通过这一个性质，加上网络N前后两次的topo序列，我们不难发现，结尾网络topo序列的最后一个肯定是在操作中失去出度而从初始的topo序列降为（或停留）最后面，所以，将其可反转的入度边反向，肯定不会存在回射边从而产生环结构，因此，从最后一个点向前搜索，每次执行可执行的反转操作，那么一定能保持当前点的不存在回射边。
对于一个点，可存在同时支配多条可反转边，因为答案要求一次一次执行反转，如果对于同一个点顺序不当可能出现环，所以我们考虑以下问题：x->y, x->z,如果反转（x,y）从而导致了环的出现，那么可以肯定z->y是成立的，而在topo关系上z比y靠前，所以我们对于同一个点输出结果时，要按照其初始网络的topo顺序，从左向右输出。
思路完毕，AC，证明....略了吧，我证明了一草稿纸。
注意不要用矩阵，我因为那个吃了几次CE......
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define N 1100
#define M 10010
using namespace std;
int n, m;
struct edge
{
int u, v, next;
} et[2][M];
int eh[2][N], tot[2];
int be[2 * N], ed[2 * N], sta[2 * N];
int deg[2][N], deg2[N];
int g[N][N];
void add(int u, int v, int i)
{
int t = ++tot[i];
et[i][t].u = u;
et[i][t].v = v;
et[i][t].next = eh[i][u];
eh[i][u] = t;
deg[i][v]++;
}
int topo(int eh[], edge et[], int que[], int deg[])
{
int i, j, k, top = -1, qt = 0;
for (i = 1; i <= n; ++i)
deg2[i] = deg[i];
for (i = 1; i <= n; ++i)
if (deg2[i] == 0)
sta[++top] = i;
for (j = 1; j <= n; ++j)
{
if (top == -1) return 0;
int u = sta[top--];
que[qt++] = u;
for (i = eh[u]; i != -1; i = et[i].next)
{
deg2[et[i].v]--;
if (deg2[et[i].v] == 0) sta[++top] = et[i].v;
}
}
return 1;
}
int was[M], cnt;
void slove()
{
int i, j, k;
memset(was, 0, sizeof(was));
printf("%d\n", cnt);
for (i = n - 1; i >= 0; --i)
{
int u = ed[i];
for (j = 0; j < n; ++j)
if (g[u][be[j]] > 0)
{
if (was[g[u][be[j]]] == 0)
{
was[g[u][be[j]]] = 1;
printf("%d ", g[u][be[j]]);
}
}
}
if (cnt > 0) printf("\n");
}
int main()
{
int i, j, k;
while (scanf("%d%d", &n, &m) != EOF)
{
memset(eh, -1, sizeof(eh));
memset(deg, 0, sizeof(deg));
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
g[i][j] = 0;
tot[1] = tot[0] = 0;
cnt = 0;
int flag = 1;
for (i = 1; i <= m; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, 0);
if (c)
{
add(b, a, 1);
cnt++;
if (g[a][b] > 0) flag = 0;
g[a][b] = i;
}
else
add(a, b, 1);
}
if (flag == 0)
{
printf("-1\n\n");
continue;
}
int first = topo(eh[0], et[0], be, deg[0]);
int last = topo(eh[1], et[1], ed, deg[1]);
if (!(first && last))
{
printf("-1\n\n");
continue;
}
slove();
printf("\n");
}
return 0;
}
posted on 2011-10-15 22:12
LLawliet 阅读(120)
评论(0) 编辑 收藏 引用 所属分类:
图论