2014
02-24

# 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

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 +１<= 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);
}else{
}