首页 > ACM题库 > HDU-杭电 > HDU 3472-HS BDC-网络流-[解题报告]HOJ
2014
03-31

HDU 3472-HS BDC-网络流-[解题报告]HOJ

HS BDC

问题描述 :

IELTS is around the corner! love8909 has registered for the exam, but he still hasn’t got prepared. Now he decides to take actions. But when he takes out the New Oriental IELTS Vocabulary, he finds there are so many words. But love8909 doesn’t get scared, because he has got a special skill. If he can make a list with some meaningful words, he will quickly remember these words and will not forget them. If the last letter of some word Wa is the same as the first letter of some word Wb, then you can connect these two words and make a list of two words. If you can connect a word to a list, you will make a longer list.

While love8909 is making the list, he finds that some words are still meaningful words if you reverse them. For example, if you reverse the word “pat”, you will get another meaningful word “tap”.

After scanning the vocabulary, love8909 has found there are N words, some of them are meaningful if reversed, while others are not. Now he wonders whether he can remember all these words using his special skill.

The N-word list must contain every word once and only once.

输入:

An integer T (T <= 50) comes on the first line, indicating the number of test cases.

On the first line of each test cases is an integer N (N <= 1000), telling you that there are N words that love8909 wants to remember. Then comes N lines. Each of the following N lines has this format: word type. Word will be a string with only ‘a’~’z’, and type will be 0(not meaningful when reversed) or 1(meaningful when reversed). The length of each word is guaranteed to be less than 20.

输出:

An integer T (T <= 50) comes on the first line, indicating the number of test cases.

On the first line of each test cases is an integer N (N <= 1000), telling you that there are N words that love8909 wants to remember. Then comes N lines. Each of the following N lines has this format: word type. Word will be a string with only ‘a’~’z’, and type will be 0(not meaningful when reversed) or 1(meaningful when reversed). The length of each word is guaranteed to be less than 20.

样例输入:

3
6
aloha 0
arachnid 0
dog 0
gopher 0
tar 1
tiger 0
3
thee 1
earn 0
nothing 0
2
pat 1
acm 0

样例输出:

Case 1: Well done!
Case 2: Well done!
Case 3: Poor boy!

Hint
In the first case, the word “tar” is still meaningful when reversed, and love8909 can make a list as “aloha-arachnid-dog-gopher-rat-tiger”. In the second case, the word “thee” is still meaningful when reversed, and love8909 can make a list as “thee-earn-nothing”. In the third case, no lists can be created.

九野的博客,转载请注明出处:http://blog.csdn.net/acmmmm/article/details/13799337

 

题意:

T个测试数据

n串字符 能否倒过来用(1表示能倒着用)

问能否把所有字符串 首尾相接

 

 欧拉回路是图G中的一个回路,经过每条边有且仅一次,称该回路为欧拉回路。具有欧拉回路的图称为欧拉图,简称E图。

无向图欧拉回路:所有点度 为偶数 && 连通

 

欧拉通路允许有且仅有2个奇度数的点(欧拉回路属于欧拉通路)

 

有向图存在欧拉回路的充要条件

一个有向图存在欧拉回路,所有顶点的入度等于出度且该图是连通图,或者 一个顶点的度数为1,另一个度数为-1,其他顶点的度数为0。

 

混合图存在欧拉回路条件:

混合图就是有向边和无向边同时存在。

把所有无向边任意定向得到有向图,若有向图存在欧拉回路则原图存在欧拉回路

 

这样会出现一个问题:对于某一点: 入度 != 出度

也就是说,对于实际上的欧拉回路,每个无向边都有一个确定的方向,如何确定这些无向边的方向,就用网络流来判断

 

有向边方向是确定的,所以不需要加入网络流来判断方向

 

此题中单词若不能倒着用可以视为有向边,能倒着用就是无向边

http://yzmduncan.iteye.com/blog/1149049

 

.

欧拉回路要求出度=入度 ,因此若出度与入度 差为奇数,一定没有欧拉回路 ch[i]%1 必须==0

用并查集判连通性

对于所有的点,总入度 + 总出度 = 0 【1】

ch[i]表示字母i+‘a’ 的入度-出度的值

由【1】式推出 所有 ch[i] < 0的点 + ch[i]>0 的点 = 0

所以 让所有ch[i]<0 点与源点建边 ,权值为 -ch[i]

ch[i]>0 与汇点建边,权值为 ch[i]

若dinic满流,表示上述式子成立,则存在回路

 

下面代码没有将每个点拆成 a和a’ 来区分入度和出度(不拆也能做,拆了更直观)

在上面把无向边任意定向(过程就是,以任意一端为入度,另一端为出度)

这样会导致:图中某些点 的度 != 0,即边入的太多了(或出的太多了)

 

网络流判欧拉回路证明:

把所有缺入度的点 连到源点(边权为该点缺的入度) 这个点连着它所有能连到的出度 边的点  =》若满流,则该点的入度 == 该点的出度,即该点符合条件

 

注意: 缺入度 和 缺出度的点 中间连着的边就是无向边 (被流过就说明这条边 需要被反向)

这样,无向边被定向后,(该边被流过就说明定向错误,该边需要反向)用网络流判断每条无向边的方向,就能得到一个欧拉回路的解

 

 

 

#include <stdio.h>
#include <string.h>
#include <queue>
#define inf 10000
#define ll short
#define end End

using namespace std;

struct Edge{
	short from, to, cap, nex;
}edge[1007];
short head[28], edgenum;
void addedge(short u, short v, short cap){
	Edge E ={u, v, cap, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++;
	Edge E_ = {v,u,0,head[v]};
	edge[edgenum] = E_;
	head[v] = edgenum++;
}

short sign[28];
bool BFS(short from, short to){
	memset(sign, -1, sizeof(sign));
	sign[from] = 0;

	queue<short>q;
	q.push(from);
	while( !q.empty() ){
		int u = q.front(); q.pop();
		for(short i = head[u]; i!=-1; i = edge[i].nex)
		{
			short v = edge[i].to;
			if(sign[v]==-1 && edge[i].cap)
			{
				sign[v] = sign[u] + 1, q.push(v);
				if(sign[to] != -1)return true;
			}
		}
	}
	return false;
}
short Stack[4], top, cur[4];
short dinic(short from, short to){
	short ans = 0;
	while( BFS(from, to) )
	{
		memcpy(cur, head, sizeof(head));
		short u = from;		top = 0;
		while(1)
		{
			if(u == to)
			{
				short flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
				for(short i = 0; i < top; i++)
					if(flow > edge[ Stack[i] ].cap)
					{
						flow = edge[Stack[i]].cap;
						loc = i;
					}

					for(short i = 0; i < top; i++)
					{
						edge[ Stack[i] ].cap -= flow;
						edge[Stack[i]^1].cap += flow;
					}
					ans += flow;
					top = loc;
					u = edge[Stack[top]].from;
			}
			for(short i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
				if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
			if(cur[u] != -1)
			{
				Stack[top++] = cur[u];
				u = edge[ cur[u] ].to;
			}
			else
			{
				if( top == 0 )break;
				sign[u] = -1;
				u = edge[ Stack[--top] ].from;
			}
		}
	}
	return ans;
}
ll n;
char ss[22];
short ch[27], f[27];
bool use[27];
short start, end;

short find(short x){return x==f[x]?x:(f[x]=find(f[x]));}
void Union(short x, short y){
	short fx = find(x), fy = find(y);
	short temp = fx; if(fx>fy){fx=fy;fy=temp;}
	f[fx] = fy;
}
int main(){
	short T, i, j, Cas = 1; scanf("%d",&T);
	while(T--)
	{
		memset(ch, 0, sizeof(ch));
		memset(use,0, sizeof(use));
		for(i=0;i<27;i++)f[i] = i;
		memset(head, -1,sizeof(head)), edgenum = 0;

		scanf("%d",&n);
		for(i = 0; i < n; i++)
		{
			scanf("%s %d",ss,&j);
			int a = ss[0]-'a', b = ss[strlen(ss)-1] - 'a';
			ch[a]++, ch[b]--;
			use[a] = use[b] = true;
			Union(a,b);

			if(j)addedge(a,b,1);
		}
		printf("Case %d: ",Cas++);
		bool ok = true;
		for(i=0;i<26;i++)
			if(use[i])
			{
				j = i;
				for(i++;i<26;i++)
					if(use[i] && find(j)!=find(i))ok = false;
				break;
			}
			short num = 0;
			for(i=0;i<26;i++)if(use[i] &&  ch[i]%2)
			{
				num++;
				if(ch[i]<0)start = i;
				else end = i;
			}
			if(num == 1 || num>2)ok = false;
			if(!ok){ printf("Poor boy!\n"); continue;}
			if(num == 2)addedge(end, start, 1);
			start = 26, end = 27;
			short sum = 0;
			for(i=0;i<26;i++)if(ch[i] && use[i] && i!=end && i!=start)
			{
				if(ch[i]<0)
					addedge(start,i,-ch[i]/2), sum-=ch[i]/2;
				else
					addedge(i,end, ch[i]>>1);
			}
			if(sum != dinic(start, end))
				printf("Poor boy!\n");
			else 
				printf("Well done!\n");

	}
}

 

参考:http://blog.csdn.net/acmmmm/article/details/13799337


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!