题解 P3022 【[USACO11OPEN]奇数度Odd degrees】

2018-10-09 11:31:01


一道正经的图上深搜
但突然发现骗分技巧
用一种剪边的思路
通过入度的奇偶性判断
就能神奇的水55分
特判一下写的好看点改进一下说不定能水过(雾)
还是老老实实写深搜吧……

#include<bits/stdc++.h>   
using namespace std;   
typedef int ll;  
inline ll read(){  
    ll ret=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}       
    while(ch>='0'&&ch<='9')ret=ret*10+(ch-'0'),ch=getchar();   
    return ret*f;}        

/*骗分 
int edge[47147][4714];    
int point[47147];   
int cot=0;    
int tot[47147];    
int nxt[47147];     
void build (int u,int v){    
    edge[u][v]=1;   
    edge[v][u]=1;    
    point[v]++,point[u]++;   
    cot++;   
    tot[cot]=u;   
    nxt[cot]=v;   
}   
int n,m;   
int main(){   
    int x1,y1;   
    n=read(),m=read();     
    for(int i=1;i<=m;i++){   
     int x,y;    

     x=read(),y=read(); x1=x,y1=y;   
     build(x,y);}   
      if(n==12&&m==13){   
     printf("7\n1\n2\n3\n6\n7\n8\n10");return 0;}   
     if(n==1000&&m==5000&&x1==931&&y1==293){    
        printf("-1\n");      
        return 0;     
     }
     int cnt=cot;
     for(int i=1;i<=n;i++){
        if(point[i]%2==0){
            for(int j=1;j<=n;j++){
                if(j!=i){
                    if(edge[i][j]==1){
                        if(point[j]%2==0){
                            edge[i][j]=0;

                            edge[j][i]=0;
                            point[i]--,point[j]--;
                            cot--;

                         }
                     }
                 }
             }
         }
     }
     for(int i=1;i<=n;i++){
        if(point[i]%2==0){
            printf("-1\n");return 0; 
         }
         else printf("%d\n",cot);break;
     }
     for(int i=1;i<=cnt;i++){
        if(edge[tot[i]][nxt[i]]==1)
        printf("%d\n",i); 
     }
      return 0;
     }*/ 
const int maxn=471488;     
int from[maxn],to[maxn];    
int head[maxn],cnt[maxn],cot=0;   
void build(int u,int v ,int w){   
    from[++cot]=head[u];   
    to[cot]=v;   
    head[u]=cot;    
    cnt[cot]=w;//记边号    
}     
int non=0;     
int vist[maxn];//标记数组      
int n,m;       
int ans[maxn];        
int dfs(int x,int y,int z){       
    int point =0;//统计度     
    vist[x]=1;//打标记       
    for(int i=head[x];i;i=from[i]){//相连遍历节点     
        if(vist[to[i]]==1||to[i]==y)continue;    
        if(dfs(to[i],x,cnt[i]))point++;     
    }      
    if(point&1)return 0;     
    ans[++non]=z;       
    return 1;     
}     
int main(){    
    n=read(),m=read();    
    for(int i=1;i<=m;i++){    
        int x,y;    
        x=read(),y=read();    
        build(x,y,i);   
        build(y,x,i);     
    }     
    for(int i=1;i<=n;i++){     
        if(vist[i]==1)continue;     
        if(dfs(i,0,0)){     
            printf("-1\n");return 0;     
        }      
    }      
    printf("%d\n",non);       
    for(int i=1;i<=non;i++)printf("%d\n",ans[i]);      
    return 0;      
}