首页 > 搜索 > DFS搜索 > HDU 1646 Network Wars-DFS-[解题报告] C++
2013
12-21

HDU 1646 Network Wars-DFS-[解题报告] C++

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 ?
{Paskill/Lisper} trapped 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

题目详解出自 论文 Amber-最小割模型在信息学竞赛中的应用

 

题目大意: 给出一个带权无向图 G = (V,E), 每条边 e属于E都有一个权值We,求一个割边集C,使得该割边集的平均边权最小,即最小化:

1.  

将等式转换,引入x向量,Xi取值为(0,1),得到0-1分数规划常规式:

2.      

将其转换得到一个关于的一个函数:

3.      

其中为单调递减函数, 当且仅当  = 0 , 为最优值.

然后我们可以二分枚举最优值 , 然后判定当前最优值是否符合要求.

判定思路:  对于每一条边权Wi 变换成了新的边权 , 而向量X(x1,x2,..,xm)表示对应边取或者不取,所以根据其取与不取划分成一个ST集。

令取为1,则 函数就转换成了 最小割的容量了(即最大流)。

有个要注意的地方,一个是枚举的最优值是一个浮点数,还有就是当 < 0 时,必定是取得,因为它能使最优值尽可能小。

最终结果可以得出最优值后,然后在跑一次最大流,然后从源点S开始DFS标记所有可以访问到的顶点,然后求出所有取得边。注意

 < 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];
int head[MAXN], idx;

void AddEdge(int a,int b,double f){
    edge[idx].u = a, edge[idx].v = b, edge[idx].f = f;
    edge[idx].nxt = head[a], head[a] = idx++;
    edge[idx].u = b, edge[idx].v = a, edge[idx].f = 0;
    edge[idx].nxt = head[b], head[b] = idx++;
}
double CreateGraph(double MaxW){
    memset( head, -1, sizeof(head));
    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;
        else AddEdge(a,b,c-MaxW),AddEdge(b,a,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;
}

 

解题报告转自:http://www.cnblogs.com/yefeng1627/p/3176567.html


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

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

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

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

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