題意：
????? 給你一些字符串，有的字符串反過來也有意義，題目問給的這n個字符串是否可以首尾相連，組成一個串。

思路：
????? 算是混合歐拉的基礎(chǔ)題目了，混合歐拉就是專門處理這類問題的，先說下混合歐拉的大體步驟。
（1） 判斷整個圖是否連通，如果不連通直接不行（方法隨意，并查集搜索什么的都行）
（2） 看度數(shù)差為奇數(shù)的有多少個，只能有0個或者兩個，其他的都不行。
（3） 如果度數(shù)差有奇數(shù)的有兩個，那么一定一個是正的v1，一個是負(fù)的v2，add(v1?????? ,v2 ,1);
（4） 如果方向隨意的邊，那么我們隨意建立一條就行add(a ,b ,1),方向固定的不用管
（5） 虛擬超級遠(yuǎn)點(diǎn)s，超級匯點(diǎn)e，然后所有度數(shù)為負(fù)數(shù)的add(s ,i ,-du[i]/2),所有為????? 正的add(i ,e ,du[i]/2);
（6） 最后一遍最大流，看是否滿流，如果滿流，那么就是有解，否則無解。
至于為什么費(fèi)用留可以這樣求，等比賽回來再來詳細(xì)補(bǔ)充這個問題。

?

?

#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;
}
?????
?????
?????
?????
?????
?????
?????

?

總結(jié)

以上是生活随笔為你收集整理的hdu3472 混合欧拉的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。