hdu3472 混合欧拉

题意：

给你一些字符串，有的字符串反过来也有意义，题目问给的这n个字符串是否可以首尾相连，组成一个串。

思路：

      算是混合欧拉的基础题目了，混合欧拉就是专门处理这类问题的，先说下混合欧拉的大体步骤。

（1）判断整个图是否连通，如果不连通直接不行（方法随意，并查集搜索什么的都行）

（2）看度数差为奇数的有多少个，只能有0个或者两个，其他的都不行。

（3）如果度数差有奇数的有两个，那么一定一个是正的v1，一个是负的v2，add(v1       ,v2 ,1);

（4）如果方向随意的边，那么我们随意建立一条就行add(a ,b ,1),方向固定的不用管

（5）虚拟超级远点s，超级汇点e，然后所有度数为负数的add(s ,i ,-du[i]/2),所有为      正的add(i ,e ,du[i]/2);

（6）最后一遍最大流，看是否满流，如果满流，那么就是有解，否则无解。

至于为什么费用留可以这样求，等比赛回来再来详细补充这个问题。

#include<queue>

#include<stdio.h>

#include<string.h>

#define N_node 30

#define N_edge 10000

#define INF 100000000

using namespace std;

typedef struct

{

int to ,next ,cost;

}STAR;

typedef struct

{

int x ,t;

}DEP;

STAR E[N_edge];

DEP xin ,tou;

int list[N_node] ,listt[N_node] ,tot;

int du[N_node] ,deep[N_node];

int mer[N_node];

void add(int a, int b ,int c)

{

   E[++tot].to = b;

   E[tot].cost = c;

   E[tot].next = list[a];

   list[a] = tot;



   E[++tot].to = a;

   E[tot].cost = 0;

   E[tot].next = list[b];

   list[b] = tot;

}

int minn(int x ,int y)

{

return x < y ? x : y;

}

int finds(int x)

{

return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

bool BFS_Deep(int s ,int t ,int n)

{

   memset(deep ,255 ,sizeof(deep));

   queue<DEP>q;

   xin.x = s ,xin.t = 0;

   q.push(xin);

   deep[xin.x] = xin.t;

   while(!q.empty())

   {

      tou = q.front();

      q.pop();

      for(int k = list[tou.x] ;k ;k = E[k].next)

      {

         xin.x = E[k].to;

         xin.t = tou.t + 1;

         if(deep[xin.x] != -1 || !E[k].cost) continue;

         deep[xin.x] = xin.t;

         q.push(xin);

      }

   }

   for(int i = 0 ;i <= n ;i ++)

   listt[i] = list[i];

   return deep[t] != -1;

}

int DFS_Flow(int s ,int t ,int flow)

{

   if(s == t) return flow;

   int nowflow = 0;

   for(int k = listt[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      int c = E[k].cost;

      listt[s] = k;

      if(deep[to] != deep[s] + 1 || !c) continue;

      int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));

      nowflow += tmp;

      E[k].cost -= tmp;

      E[k^1].cost += tmp;

      if(nowflow == flow) break;

   }

   if(!nowflow) deep[s] = 0;

   return nowflow;

}

int DINIC(int s ,int t ,int n)

{

   int Ans = 0;

   while(BFS_Deep(s ,t ,n))

   {

      Ans =+ DFS_Flow(s ,t ,INF);

   }

   return Ans;

}

int main ()

{

   int n ,i ,j ,a ,b ,c;

   int mark[30];

   int t ,cas = 1;

   char str[30];

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      memset(list ,0 ,sizeof(list)) ,tot = 1;

      memset(du ,0 ,sizeof(du));

      memset(mark ,0 ,sizeof(mark));

      for(i = 1 ;i <= 26 ;i ++) mer[i] = i;



      for(i = 1 ;i <= n ;i ++)

      {

         scanf("%s %d" ,str ,&c);

         a = str[0] - 'a' + 1;

         b = str[strlen(str)-1] - 'a' + 1;

         du[a] -- ,du[b] ++;

         mark[a] = mark[b] = 1;

         mer[finds(a)] = finds(b);

         if(c) add(a ,b ,1);

      }



      int sum = 0;

      for(i = 1 ;i <= 26 && sum <= 2;i ++)

      if(finds(i) == i && mark[i]) sum ++;

      printf("Case %d: " ,cas ++);

      if(sum != 1)

      {

         puts("Poor boy!");

         continue;

      }



      sum = 0;

      int v1 ,v2;

      for(i = 1 ;i <= 26 ;i ++)

      {

         if(du[i] % 2 && du[i] < 0) v1 = i ,sum ++;

         if(du[i] % 2 && du[i] > 0) v2 = i ,sum ++;

      }

      if(sum != 0 && sum != 2)

      {

          puts("Poor boy!");

          continue;

      }

      if(sum == 2)

      {

         add(v1 ,v2 ,1);

         du[v1] -- ,du[v2] ++;

      }



      sum = 0;

      for(i = 1 ;i <= 26 ;i ++)

      {

         if(!mark[i]) continue;

         if(du[i] < 0) add(0 ,i ,-du[i]/2) ,sum -= du[i]/2;

         else add(i ,27 ,du[i]/2);

      }

      DINIC(0 ,27 ,27) == sum ? puts("Well done!"):puts("Poor boy!");

   }

   return 0;

}

巴特西

hdu3472 混合欧拉

最新文章

热门文章