[POI2011]SMI-Garbage

题目描述

http://main.edu.pl/en/archive/oi/18/smi

The Byteotian Waste Management Company (BWMC) has drastically raised the price of garbage collection lately. This caused some of the citizens to stop paying for collecting their garbage and start disposing of it in the streets. Consequently, many streets of Byteburg are literally buried under litter.

The street system of Byteburg consists of intersections, some of which are directly connected with bidirectional streets. No two streets connect the same pair of intersections. Some of the streets are littered while others are not.

The mayor of Byteburg, Byteasar, has decided on an unprecedented action to persuade the citizens to pay for waste collection. Namely, he decided to clean only some of the streets - precisely those that the majority of people living on paid for garbage collection. The streets that the majority of people living on did not pay for waste collection, on the other hand, will thus remain littered - or if it is called for - will become littered by the garbage collected from other streets! Byteasar has already prepared a city map with the streets to be cleaned and to remain or become littered marked on. Unfortunately, the BWMC employees cannot comprehend his master plan. They are, however, quite capable of carrying out simple instructions.

A single such instruction consists in driving the garbage truck along a route that starts on an arbitrary intersection, goes along any streets of choice, and ending on the very same intersection that it started on. However, every intersection can be visited at most once on a single route, except for the one it starts and ends with-the garbage truck obviously appears twice on that one. The truck cleans a littered street it rides along, but on the other hand it dumps the waste on the clean streets along its route, making them littered.

Byteasar wonders if it is possible to execute his plan by issuing a number of aforementioned route instructions. Help him out by writing a program that determines a set of such routes or concludes that it is impossible.

给定n个点m条边，每条边有一个初始权值0或1，有一个最终权值0或1，每次可以给一个简单环上的边权值异或1，求一种方案使得每条边从初始权值变成最终权值，无解输出"NIE"

输入输出样例

输入样例#1：

输出样例#1：

2

3 1 3 2 1

3 4 6 5 4

分析：
模板题em。。。欧拉回路中最简单的一道题。。。然而我不会？？？因为我第一个做这题的。。。

CODE：
来源于https://loj.ac/submission/512425

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 const int maxn = 1e5 + ;

 const int maxm = 2e6 + ;

 using namespace std;

 int cnt;

 int d[maxn];

 int to[maxm];

 int nex[maxm];

 int last[maxn], k = ;

 int q[maxn], top;

 int inq[maxn];

 int vis[maxm];

 vector<int> ans[maxn];

 inline int read() {

     int x = ;

     char ch = getchar();

     while (ch < '' || ch > '') ch = getchar();

     while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar();

     return x;

 }

 int rit[], rits;

 void write(int x) {

     for (int i; x; x = i) i = x / , rit[++rits] = x - i * ;

     while (rits) putchar(rit[rits--] + '');

 }

 inline void add_edge(int x, int y) {

     to[++k] = y;

     nex[k] = last[x];

     last[x] = k;

 }

 void dfs(int x) {

     if (inq[x]) {

         ++cnt;

         int y = ;

         do

             y = q[top--], inq[y] = , ans[cnt].push_back(y);

         while (y != x);

     }

     for (int &i = last[x]; i; i = nex[i])

         if (!vis[i])

             vis[i] = vis[i ^ ] = , inq[q[++top] = x] = , dfs(to[i]);

 }

 int main(void) {

     int n = read(), m = read();

     while (m--) {

         int x = read(), y = read(), a = read(), b = read();

         if (a ^ b) {

             add_edge(x, y);

             add_edge(y, x);

             d[x] ^= ;

             d[y] ^= ;

         }

     }

     for (register int i = ; i <= n; i++)

         if (d[i]) {

             cout << "NIE\n";

             return ;

         }

     for (register int i = ; i <= n; i++) dfs(i);

     write(cnt), putchar('\n');

     for (register int i = ; i <= cnt; i++) {

         write(ans[i].size()), putchar(' ');

         for (int j = ; j < ans[i].size(); j++) write(ans[i][j]), putchar(' ');

         write(ans[i][]), putchar('\n');

     }

     return ;

 }

巴特西

[POI2011]SMI-Garbage

题目描述

输入输出样例

最新文章

热门文章