设为首页 加入收藏

TOP

codeforces 547D Mike and Fish 欧拉路径
2015-11-21 01:00:45 来源: 作者: 【大 中 小】 浏览:1次
Tags：codeforces 547D Mike and Fish 路径

题意：

给定二维平面上的n个点的坐标

问：

把每个点用红色或蓝色染色， 使得 水平共线（或者垂直共线）的 点 中红色与蓝色数量差不超过1.

思路：

我们建一个二部图，X集是x轴，Y集是y轴

那么点(1,5)就是 x集的 1向 y集的 5连一条边。

此时点就是用边来表示的，那我们的任务就是给边染色。

使得：

对于二部图中任意一个点， 点所连接的红边和蓝边数量差不超过1.

那么我们可以认为这个点的入边就是红色，出边就是蓝色。显然这就是一个欧拉路径。

所以爆搜欧拉路径即可。

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; template 
              
                inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template 
               
                 inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } const int N = 2e5 + 10; typedef long long ll; struct Edge{ int from, to, col, nex; }edge[N << 2]; int head[N<<1], edgenum; void add(int u, int v){ Edge E = { u, v, -1, head[u] }; edge[edgenum] = E; head[u] = edgenum++; } int n; int vis[N << 2]; int du[N << 2]; void dfs(int u){ // printf("%d ", u); for (int i = head[u]; ~i; i = head[u] = edge[i].nex){ if (edge[i].col != -1)continue; int v = edge[i].to; edge[i].col = u < v; edge[i ^ 1].col = -2; vis[u]++; vis[v]++; dfs(v); break; } } vector
                
                 X, Y; int x[N], y[N]; int main(){ rd(n); memset(head, -1, sizeof head); edgenum = 0; for (int i = 1; i <= n; i++){ rd(x[i]); rd(y[i]); X.push_back(x[i]); Y.push_back(y[i]); } sort(X.begin(), X.end()); sort(Y.begin(), Y.end()); X.erase(unique(X.begin(), X.end()), X.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end()); for (int i = 1; i <= n; i++){ x[i] = lower_bound(X.begin(), X.end(), x[i]) - X.begin() ; y[i] = lower_bound(Y.begin(), Y.end(), y[i]) - Y.begin() + n; du[x[i]]++; du[y[i]]++; add(x[i], y[i]); add(y[i], x[i]); } // for (int i = 0; i <= 2 * n; i++)printf("(%d,%d)\n", i, du[i]); for (int i = 0; i <= 2 * n; i++) if (du[i] & 1 && vis[i] < du[i]){ // printf("odd dfs %d: ", i); dfs(i); // puts(""); } for (int i = 0; i <= 2 * n; i++) if (du[i] && vis[i] < du[i]){ // printf("normal dfs %d: ", i); dfs(i); // puts(""); } for (int i = 0; i < edgenum; i ++) if (edge[i].col >= 0) putchar(edge[i].col ? 'r' : 'b'); return 0; } /* 4 1 1 1 2 2 1 2 2 7 1 0 2 0 2 1 0 2 1 2 2 2 2 3 */


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu 2088 Box of Bricks 下一篇：POJ 1845-Sumdiv(快速幂取模+整数..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: