pku 3409 并查集+欧拉回路+输入处理.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3409 并查集+欧拉回路+输入处理
//注意输入的x,y坐标会是250个字符，所以不能用int,__int64来存全部当字符串处理
//同时忽略掉开头为零的部分，比如00450，看成450
//#define NMAX 
//#define INFI 
#define PI 3.1415926
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back
#define NMAX 7005
#define PMAX 255

typedef struct oopnode
{
    int fa;
    int rank;
    int du;
    char x[PMAX];
    char y[PMAX];
}oopnode;

typedef struct oopline
{
    char x1[PMAX];
    char x2[PMAX];
    char y1[PMAX];
    char y2[PMAX];
}oopline;

oopline line[NMAX];
oopline qline[NMAX];
oopnode node[2*NMAX];
oopnode temp[2*NMAX];

int getroot(int x)
{
    int root,tmp=x;
    while(node[tmp].fa!=-1) tmp=node[tmp].fa;
    root=tmp;
    while(node[x].fa!=-1)
    {
        tmp=node[x].fa;
        node[x].fa=root;
        x=tmp;
    }
    return root;
}

void join(int a,int b)
{
    a=getroot(a);
    b=getroot(b);
//    printf("join %d %d\n",a,b);
    if(a!=b)
    {
        if(node[a].rank<node[b].rank)
        {
            node[b].rank+=node[a].rank;
            node[a].fa=b;
        }
        else
        {
            node[a].rank+=node[b].rank;
            node[b].fa=a;
        }
    }
}

int cmp(const void *a,const void *b)
{
    if(strcmp(((oopnode *)a)->x,((oopnode *)b)->x)==0) return strcmp(((oopnode *)a)->y,((oopnode *)b)->y);
    else return strcmp(((oopnode *)a)->x,((oopnode *)b)->x);
}
/*
bool cmpl(oopline a,oopline b)
{
    if(a.x1==b.x1)
    {
        if(a.x2==b.x2)
        {
            if(a.y1==b.y1)
            {
                return a.y2<b.y2;
            }
            return a.y1<b.y1;
        }
        else return a.x2<b.x2;
    }
    else return a.x1>b.x1;
}
*/
int search(oopnode xx,int num)
{
    oopnode *key;
 //   printf("xx=%d %d\n",xx.x,xx.y);
    key=(oopnode *)bsearch(&xx,&node[1],num,sizeof(oopnode[1]),cmp);
    return key-node;
}

void solve(int num)
{
    int i,j,s1,s2,jnum,tr;
    oopnode m;
//    sort(qline+1,qline+1+num,cmpl);
    strcpy(line[1].x1,qline[1].x1);
    strcpy(line[1].x2,qline[1].x2);
    strcpy(line[1].y1,qline[1].y1);
    strcpy(line[1].y2,qline[1].y2);
    for(i=2,j=1;i<=num;i++)
    {
//        if(!(qline[i].x1==qline[i-1].x1 && qline[i].x2==qline[i-1].x2 && qline[i].y1==qline[i-1].y1 && qline[i].y2==qline[i].y1))
//        {
            ++j;
            strcpy(line[j].x1,qline[i].x1);
             strcpy(line[j].x2,qline[i].x2);
            strcpy(line[j].y1,qline[i].y1);
            strcpy(line[j].y2,qline[i].y2);
//        }
    }
   for(i=1,j=1;i<=num;i++)
    {
     strcpy(temp[j].x,line[i].x1);
     strcpy(temp[j].y,line[i].y1);
     j++;
     strcpy(temp[j].x,line[i].x2);
     strcpy(temp[j].y,line[i].y2);
     j++;
    }
    qsort(temp+1,2*num,sizeof(oopnode),cmp);
    strcpy(node[1].x,temp[1].x);
    strcpy(node[1].y,temp[1].y);
    for(i=2,j=1;i<=2*num;i++)
    {
        if(!(strcmp(temp[i].x,temp[i-1].x)==0 && strcmp(temp[i].y,temp[i-1].y)==0)) 
        {
            j++;
            strcpy(node[j].x,temp[i].x);
            strcpy(node[j].y,temp[i].y);
        }
    }
    jnum=j;
 //   for(i=1;i<=jnum;i++) printf("x=%d y=%d\n",node[i].x,node[i].y);
    for(i=1;i<=jnum;i++) 
    {
        node[i].fa=-1;
        node[i].rank=1;
        node[i].du=0;
    }
    for(i=1;i<=num;i++)
    {
 //       printf("line=%d %d %d %d\n",line[i].x1,line[i].y1,line[i].x2,line[i].y2);
        strcpy(m.x,line[i].x1);
        strcpy(m.y,line[i].y1);
        s1=search(m,jnum);
 //       printf("s1=%d  ",s1);
        node[s1].du++;
        strcpy(m.x,line[i].x2);
        strcpy(m.y,line[i].y2);
        s2=search(m,jnum);
        node[s2].du++;
//       printf("s2=%d\n",s2);
        join(s1,s2);
    }
 //   for(i=1;i<=jnum;i++) printf("i=%d fa=%d\n",i,node[i].fa);
    tr=getroot(1);
    for(i=2;i<=jnum;i++)
    {
     if(tr!=getroot(i))
     {
         printf("0\n");
         return;
     }
    }
    for(i=1;i<jnum;i++)
    {
        if(node[i].du%2==1)
        {printf("0\n");return;}
    }
    printf("1\n");
}


int main()
{
    int num,i,j,k;
    char w[PMAX];
    char str[255];
 //   freopen("pku.in","r",stdin);
    i=1;
    scanf("%d",&num);
//    for(i=1;i<=num;i++)
 //   {
    while(scanf("%s",str)!=EOF)
    {
        for(j=1;j<=4;j++)
        {
            if(j>1) scanf("%s",str);
			k=0;
        	while(str[k]=='0') k++;
	//		printf("k=%d\n",k);
			strcpy(w,&str[k]);	
            if(j==1) strcpy(qline[i].x1,w);
            else if(j==2) strcpy(qline[i].y1,w);
            else if(j==3) strcpy(qline[i].x2,w);
            else strcpy(qline[i].y2,w);
//			printf("w= %s\n",w);
        }
        ++i;
 //       printf("i=%d\n",i);
    }
    num=i-1;
 //   }
    solve(num);
    return 0;
}