Red Huang

Red Huang

SGU 101

歐拉環 測資有點 tricky~

只要奇點數量不是 0 跟 2 就是無解

/\*  
 \* GCA : Where is the Dp,there is the wall  
 \*/  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
using namespace std;  
#ifdef DEBUG  
#define VAR(a,b) decltype(b) a=(b)  
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#else  
#define VAR(a,b) \_\_typeof(b) a=(b)  
#define debug(...)  
#endif  
typedef long long int Int;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Pln() printf("\\n")  
#define M 106  
#define PB push\_back  
#define oo INT\_MAX  
#define X first  
#define Y second  
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)  
#define eps 1e-9  
inline bool xdy(double x,double y){return x>y+eps;}  
inline bool xddy(double x,double y){return x>y-eps;}  
inline bool xcy(double x,double y){return x<y-eps;}  
inline bool xcdy(double x,double y){return x<y+eps;}  
int m;  
int mz\[10\]\[10\];  
int ind\[10\];  
#define PIC pair<int,char\>  
struct edges{  
    int x,y;  
    int vis;  
    edges(){  
        x=y=-1;  
        vis=0;  
    }  
}edge\[M\];  
vector<PIC> ans;  
int pEdge(int x,int y){  
    for(int i=0;i<m;i++){  
        if(edge\[i\].x==x&&edge\[i\].y==y&&edge\[i\].vis==0){  
            edge\[i\].vis=1;  
            return i;  
        }else if(edge\[i\].x==y&&edge\[i\].y==x&&edge\[i\].vis==0){  
            edge\[i\].vis=1;  
            return i+m;  
        }  
    }  
    return -1;  
}  
void dfs(int now){  
    for(int i=0;i<=6;i++){  
        if(mz\[now\]\[i\]){  
            mz\[now\]\[i\]--;  
            mz\[i\]\[now\]--;  
            dfs(i);  
            int tmp=pEdge(now,i);  
            if(tmp>=m){  
                ans.PB(PIC(tmp-m,'-'));  
            }else{  
                ans.PB(PIC(tmp,'+'));  
            }  
        }  
    }  
}  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    while(~scanf("%d",&m)){  
        Set(mz,0);  
        Set(ind,0);  
        ans.clear();  
        for(int i=0;i<m;i++){  
            int x,y;  
            scanf("%d%d",&x,&y);  
            edge\[i\].vis=0;  
            edge\[i\].x=x;edge\[i\].y=y;  
            mz\[x\]\[y\]++,mz\[y\]\[x\]++;  
            ind\[x\]++,ind\[y\]++;  
        }  
        int fir=-1;  
        int cntodd=0;  
        for(int i=0;i<=6;i++){  
            if(ind\[i\]&1){  
                cntodd++;  
                fir=i;  
            }  
        }  
        if(fir==-1){  
            for(int i=0;i<=6;i++){  
                if(ind\[i\])fir=i;  
            }  
        }  
        if(cntodd!=0&&cntodd!=2){  
            puts("No solution");  
            continue;  
        }  
        dfs(fir);  
        if(ans.size()>=m)  
            for(int i=ans.size()-1;i>=0;i--){  
                int x=ans\[i\].X;  
                char y=ans\[i\].Y;  
                printf("%d %c\\n",x+1,y);  
            }  
        else puts("No solution");  
  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.