2013
12-21

# Network Wars

It is the year 2126 and comet Swift-Tuttle has struck the earth as predicted. The resultant explosion emits a large cloud of high energy neutrons that eliminates all human life. The accompanying electro-magnetic storm causes two unusual events: many of the links between various parts of the electronic network are severed, and some postgraduate AI projects begin to merge and mutate, in much the same way as animal life did several million years ago. In a very short time two programs emerge, Paskill and Lisper, which move through the network marking each node they visit: Paskill activates a modified Prolog interpreter and Lisper activates the Hello World’ program. However Hello World’ has mutated into an endless loop that so ties up the node that no other program, not even Lisper, can re-enter that node and the Prolog interpreter immediately reverse compiles (and destroys) any program that enters. However, Paskill knows which nodes it has visited and never tries to re-enter them. Thus if Lisper attempts to enter a node already visited by Paskill it will be annihilated; neither can enter a node already visited by Lisper, if either (or both) cannot move both will halt and if they ever arrive at a node simultaneously they annihilate each other. Both programs move through the network at the same speed.

Write a program to simulate these events. All nodes in the the network are labelled with a single uppercase letter as shown below. When moving to the next node, Paskill searches alphabetically forwards from the current node, whereas Lisper searches alphabetically backwards from the current node, both wrapping round if necessary. Thus, (in the absence of the other) if Paskill enters the network below at A, it would visit the nodes in the order A, B, C, D, G, H, E, F; if Lisper enters the network at H it would visit them in the order H, G, E, F. Simulation stops when one or more of the above events occurs. If more than one event occurs, mention Paskill first.

Input will consist of a series of lines. Each line will describe a network and indicate the starting nodes for the two programs. A network is described as a series of nodes separated by ;’ and terminated by a period (.’). Each node is described by its identifier, a :’ and one or more of the nodes connected to it. Each link will be mentioned at least once, as will each node, although not all nodes will be described’. After the period will appear the labels of the starting nodes–first Paskill and then Lisper. No line will contain more than 255 characters. The file will be terminated by a line consisting of a single #.

Output will consist of one line for each network. Each line will specify the terminating event and the node where it occurs. The terminating event is one or two of the following:

Lisper destroyed in node ?
Both annihilated in node ?

A:BD;C:BD;F:E;G:DEH;H:EG. A H
E:AB. A B
B:ACD. B D
A:B;B:C;D:E. A D
#

Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper destroyed in node B
Lisper trapped in node E

1.

2.

3.

< 0 的边要特殊处理。因为是负值放进去计算不太方便。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;

const int inf = 0x3f3f3f3f;
const int MAXN = 110;
const double esp = 1e-8;
int sign(double x){ return x<-esp?-1:(x>esp);}
int n, m, Max;
int S, N, T;

struct Edge{
int u, v, nxt;
double f;
}edge[50101];
struct Edge_Info{
int a,b,c;
void input(){
scanf("%d%d%d",&a,&b,&c);
}
}edge_info[550];
bool vis[MAXN];
int h[MAXN], vh[MAXN];

edge[idx].u = a, edge[idx].v = b, edge[idx].f = f;
edge[idx].u = b, edge[idx].v = a, edge[idx].f = 0;
}
double CreateGraph(double MaxW){
idx = 0;
double tmp_val = 0;
for(int i = 1; i <= m; i++){
int a = edge_info[i].a, b = edge_info[i].b, c = edge_info[i].c;
if( sign(c - MaxW) < 0 )
tmp_val += c-MaxW;
}
return tmp_val;
}
double dfs(int u,double flow){
if(u == T) return flow;
int tmp = h[u]+1; double sum = flow;
for(int i = head[u]; ~i; i = edge[i].nxt){
if( sign(edge[i].f) > 0 && (h[ edge[i].v ]+1 == h[u])){
double p = dfs( edge[i].v, min(sum,edge[i].f));
edge[i].f -= p, edge[i^1].f += p, sum -= p;
if( sign(sum)==0 || h[S]==N ) return flow-sum;
}
}
for(int i = head[u]; ~i; i = edge[i].nxt ){
if( sign(edge[i].f) > 0 ) tmp = min(tmp,h[ edge[i].v ] );
}
if( --vh[ h[u] ] == 0 ) h[S] = N;
else ++vh[ h[u]=tmp+1 ];
return flow-sum;
}
double sap(){
double maxflow = 0;
memset(h,0,sizeof(h));
memset(vh,0,sizeof(vh));
vh[0] = N;
while( h[S] < N ) maxflow += dfs( S,inf );
return maxflow;
}
double Search( double l, double r ){
while( r-l > 1e-5 ){
double mid = (r+l)/2.0;
double maxflow = CreateGraph( mid );
maxflow += sap();
if( sign(maxflow) < 0 ) r = mid;
else l = mid;
}
return l;
}
void DFS(int u){
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt){
if( sign(edge[i].f) > 0 && !vis[ edge[i].v ] )
DFS( edge[i].v );
}
}

vector<int> res;
int mp[MAXN][MAXN];

void solve(){
S = 1, T = n, N = n;
double limit = Search( 0, Max );
double maxflow = CreateGraph( limit );
maxflow += sap();
res.clear();
memset(vis,0,sizeof(vis));
DFS(S);
for(int i = 1; i <= m; i++){
mp[ edge_info[i].a ][ edge_info[i].b ] = i;
mp[ edge_info[i].b ][ edge_info[i].a ] = i;
if( sign(edge_info[i].c-limit) < 0 )
res.push_back(i);
}
for(int i = 0; i < idx; i += 2 ){ // 10000
int u = edge[i].u, v = edge[i].v;
if( vis[u] && !vis[v] && sign( edge[i].f ) == 0 ){ //500
res.push_back(  mp[u][v] );
}
}
sort( res.begin(), res.end() );
int num = res.size();
printf("%d\n", num );
for(int i = 0; i < num; i++)
printf( i==0? "%d":" %d", res[i] );
printf("\n");
}
int main(){
int Case = 1;
while( scanf("%d%d",&n,&m) != EOF) {
Max = 0;
for(int i = 1; i <= m; i++){
edge_info[i].input();
Max = max( Max, edge_info[i].c );
}
solve();
if( Case++ > 1 ) puts("");
}
return 0;
}

1. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

2. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

3. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

4. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

5. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。