noip模拟

2、世界人民大團結

greatunion.cpp/in/out

1s / 256M

【題目描述】

現在,世界的主題是和平與發展。社會學博士老 Z 認為,要實作和平發展,首先要實作

世界人民大團結。

世界上有 n 個人。他們胸前和背後各有一個自然數,大于或等于 0 且小于或等于 6。兩

個身上帶有某個相同數字的人把身上相同的數字合在一起,就實作了團結。比如,(0,1)(1,2)

就實作了團結,而(0,1)(2,1)和(0,0)(1,2)都不是團結。把數合在一起的方法,是胸靠胸、背靠

背、背靠胸或胸靠背。

請判斷世界人民能否實作大團結。如果能,請輸出大團結的實作方案。

【輸入】

第一行,一個正整數 n,表示世界上有 n 個人。

剩餘 n 行,每行是用空格隔開的兩個自然數,大于等于 0 且小于等于 6,第(1+i)行表示第 i

個人胸前和背後的數字。

【輸出】

如大團結可以實作,輸出 n 行,每行兩個空格隔開的數字。第一個是人的編号(同輸入);

第二個是“-”或“+”,

“+”表示這個人胸在前,背在後,“-”反之。人們按照你輸出的順

序和面對的方向從前到後站立。具體參見樣例。

如大團結不能實作,輸出一行“No Solution”(不含引号)

。

【樣例輸入】

5

1 2

2 4

2 4

6 4

2 1

【樣例輸出】

2 -

5 +

1 +

3 +

4 -

【資料規模】

對于 100%的資料,1<=n<=100

題解：由于每個人都要用到，就相當于一個以[0，6]為頂點，以人為邊的無項圖，大團結就是無項圖的歐拉回路。

歐拉回路存在的充要條件（在連通圖中） 每個點的度為偶數（無向圖） 每個點的入度出度相等（有向圖） 歐拉路存在的必要條件： 有且僅有兩個點的度為奇數（無向圖） 總的入度和等于總的出度和，有且僅有兩個點的入度、出度差為1，其他點相等（有向圖）。

與二分圖比對算法類似，是一個深度優先周遊的過程，時間複雜度O(M)（因為一條邊最多被通路一次）。核心代碼（邊是用邊表存儲的而不是鄰接連結清單，因為無向圖中需要對其逆向的邊進行處理，在有向圖中，可以用鄰接連結清單存儲邊）：

code;

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,map[10][10],S,T,top,ans[100010],tot,u,x[110],y[110],v,d[110];
void dfs(int u)
{
  for(int i=1;i<=7;i++)
    if(map[u][i])
      {
    map[u][i]--,map[i][u]--;
    d[u]--,d[i]--;
    dfs(i);
      }
  ans[++top]=u;
}
bool cal(int u,int v,int t)
{
  if((u==x[t]&&v==y[t])||(u==y[t]&&v==x[t]))return 1;
  return 0;
}
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
    {
      scanf("%d%d",&x[i],&y[i]);x[i]++,y[i]++;
      d[x[i]]++,d[y[i]]++;
      map[x[i]][y[i]]++,map[y[i]][x[i]]++;
    }
  for(int i=1;i<=7;i++)if(d[i]&1)tot++;
  if(tot!=0&&tot!=2){puts("No Solution");return 0;}
  for(int i=1;i<=7;i++)
    {
      if(d[i]&1)
    {
      if(S==0)S=i;
      else T=i;
    }
      if(d[i]&&!tot)S=i;
    }
  dfs(S);
  for(int i=1;i<=7;i++)
    if(d[i]){puts("No Solution");return 0;}
  for(int i=1;i<top;i++)
    for(int j=1;j<=n;j++)
      if(cal(ans[i],ans[i+1],j))//相鄰入棧一定有邊相連
      {
    printf("%d",j);
    if(x[j]==ans[i])puts(" +");
    else puts(" -");
    x[j]=y[j]=-1;
    break;
      }
  return 0;
}      

轉載于:https://www.cnblogs.com/lxykk/p/7754701.html