首页 > ACM题库 > HDU-杭电 > HDU 2983-Integer Transmission-栈-[解题报告]HOJ
2014
02-24

HDU 2983-Integer Transmission-栈-[解题报告]HOJ

Integer Transmission

问题描述 :

You’re transmitting an n -bits unsigned integer k through a simulated network. The i -th bit counting from left is transmitted at time i (e.g. 4-bit unsigned integer 5 is transmitted in this order: 0-1-0-1). The network delay is modeled as follows: if a bit is transmitted at time i , it may arrive at as early as i + 1 and as late is i + d + 1 , where d represents the maximal network delay. If more than one bit arrived at the same time, they could be received in any order.

For example, if you’re transmitting a 3-bit unsigned integer 2 (010) for d = 1 , you may receive 010, 100 (first bit is delayed) or 001 (second bit is delayed).

Write a program to find the number of different integers that could be received, and the smallest/largest ones among them.

输入:

The input contains several test cases. Each case consists of three integers n, d, k (1<=n<=64, 0<=d<=n, 0<=k < 2^n) , the number of bits transmitted, the maximal network delay, and the integer transmitted. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. Each case consists of three integers n, d, k (1<=n<=64, 0<=d<=n, 0<=k < 2^n) , the number of bits transmitted, the maximal network delay, and the integer transmitted. The last test case is followed by a single zero, which should not be processed.

样例输入:

3 0 2 
3 1 2 
10 2 888 
7 3 107 
0

样例输出:

Case 1: 1 2 2 
Case 2: 3 1 4 
Case 3: 25 490 984 
Case 4: 19 47 122

唉,这明明也是一道差不多的题目,为什么构图完之后,还是错了很久,我很不解呀,一直改,一直改,但是时间还是很慢,2766ms,SPFA+队列实现

所以很想改一下,用栈来实现,可结果却是给了我一个TLE,无语呀,不知道怎么回事,看了大牛的很快呀,差不多500ms,用SPFA+栈实现,难道是我在预处理,构图的时候,慢了?

不解呀?我自己的加边操作很方便,可是很慢吗?= =!

郁闷,看来得改改习惯了

额,都没讲下题目:

分析题意:

输入有两种形式:

1:P A B X  即 B + X = A 转化一下: B – A <= -X,  A – B <= X  构造边和权:(A, B, -X), (B, A, X)

2:V A B    即  B +1<= A 转化一下:B – A <= -1                     构造边和权:(A, B, -1) 

先贴下我这个比较水,比较慢的代码

#include<iostream>
#include<string>
#include<queue>
#define MAXINT 9999999
#define MAXN 1100
using namespace std;
int dis[MAXN],n,m,num,p[MAXN];
int vis[MAXN],cou[MAXN];
queue<int> Q;
struct edge
{
	int v,w,next;
	edge(int _next=0,int _v=0,int _w=0):next(_next),v(_v),w(_w){};
}e[MAXN*201];
bool spfa()
{
	for(int i=1;i<=n;i++)
		dis[i]=0;
	while(!Q.empty()) Q.pop();
	for(int i=1;i<=n;i++)
	{
		Q.push(i);
		vis[i]=1;
		cou[i]=1;
	}
	while(!Q.empty())
	{
		int t=Q.front();
		Q.pop();vis[t]=0;
		for(int j=p[t];j!=-1;j=e[j].next)
		{
			if(dis[e[j].v]>e[j].w+dis[t])
			{
				dis[e[j].v]=e[j].w+dis[t];
				if(!vis[e[j].v])
				{
					vis[e[j].v]=1;
					cou[e[j].v]++;					
					if(cou[e[j].v]>n)
						return false;
					Q.push(e[j].v);
				}
			}
		}
	}
	return true;
}
int main()
{
	char str;
	int a,b,c;
	while(cin>>n>>m)
	{
		 num=0;
		 memset(p,-1,sizeof(p));
		for(int i=0;i<m;i++)
		{
			cin>>str;
			if(str=='P')
			{
				cin>>a>>b>>c;
				e[num]=edge(p[a],b,c);
				p[a]=num++;
				e[num]=edge(p[b],a,-c);
				p[b]=num++;
			}
			else {
				cin>>a>>b;
				e[num]=edge(p[b],a,-1);
				p[b]=num++;
			}
		}
		if(spfa())
			cout<<"Reliable"<<endl;
		else cout<<"Unreliable"<<endl;
	}
	return 0;
}

看下用栈实现的代码:

#include<stdio.h>
#include<stdlib.h>
#define INF 0xfffffff
#define NN 1004
#define MM 200004

int edNum, N;
int next[MM];
int root[NN];
int mark[NN];
int cnt[NN];
int dis[NN];
int stack[NN];

struct node{
int e, v;
}edge[MM];
void add(int a, int b, int c){
edge[edNum].e = b;
edge[edNum].v = c;
next[edNum] = root[a];
root[a] = edNum++;
}

int Spfa()
{
int i, top, cur, tmp, nxt;
top = 0;
//初始化的时候没有加源点,直接将所有有根的点入栈,也很不错
for (i = 1; i <= N; i++){
dis[i] = INF;
// key1
if (root[i] != -1){
stack[++top] = i;
cnt[i]++;
mark[i] = 1;
}
}

while (top){
cur = stack[top--];
tmp = root[cur];
mark[cur] = 0;
while (tmp != -1){
nxt = edge[tmp].e;
//key2
if (dis[nxt] > dis[cur] + edge[tmp].v){
dis[nxt] = dis[cur] + edge[tmp].v;
if (!mark[nxt]){
cnt[nxt]++;
if (cnt[nxt] > N + 1){
return 1;
}
mark[nxt] = 1;
stack[++top] = nxt;
}
}
tmp = next[tmp];
}
}
return 0;
}
int main()
{
int i, a, b, c, M;
char str[2];

while (scanf("%d%d", &N, &M) != EOF)
{

edNum = 0;
for (i = 0; i <= N; i++){
root[i] = -1;
mark[i] = 0;
cnt[i] = 0;
}

while (M--){
scanf("%s%d%d", str, &a, &b);
if (str[0] == 'P'){
scanf("%d", &c);
add(b, a, c);
add(a, b, -c);
}else{
add(a, b, -1);
}
}
if (Spfa()){
puts("Unreliable");
}else{
puts("Reliable");
}
}
return 0;
}

解题参考:http://www.cnblogs.com/nanke/archive/2011/08/14/2137679.html