当前位置:编程学习 > 网站相关 >>

nbu 2428 Risk

 
题目大意:
有n个区域(1<=n<=100,编号1~n),第i个区域有ai个士兵(0<=ai<=100),ai为0时表示该区域为敌人区.
现在要通过一次调兵(设从a调兵,那么只能调到和a相邻的自己的区域)使得和敌人接壤的区域的最小士兵数最大,且自己的所有区域的兵的数量为正.
 
题目思路:
假设答案为x.
(1)建立一个超级源点S,并把所有的敌人的区域看成一个汇点T.
(2)将第i区域看成两个点i和i',建立一条边,容量为a[i].
(3)如果i区域和j区域相邻,
j是自己的区域,建立2条边
一条为i -> j',容量为a[i].
一条为j -> i',容量为a[j].
j是敌人的区域,建立一条边(只建立一次,即便有多个j是敌人的区域)
i' -> T ,容量为x.
(4)对于不和敌人区域相邻的点,向汇点建立一条容量为1的边.
(5)源点连向第i区域的i点,容量为a[i].
将点拆成两个点,保证了如果从i调兵到j,那么如果j和k相邻,i的兵不会再被调到k.
不拆点: i -> j -> k,显然不可取.
拆点后: i -> i' , j -> j' , k - >k'
i -> j' , j -> k' ,i和k不相连.
 
 
代码:
[cpp]  
#include <stdlib.h>  
#include <string.h>  
#include <stdio.h>  
#include <ctype.h>  
#include <math.h>  
#include <stack>  
#include <queue>  
#include <map>  
#include <set>  
#include <vector>  
#include <string>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
  
#define ll long long  
#define ls rt<<1  
#define rs ls|1  
#define lson l,mid,ls  
#define rson mid+1,r,rs  
#define middle (l+r)>>1  
#define eps (1e-8)  
#define clr_all(x,c) memset(x,c,sizeof(x))  
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))  
#define MOD 1000000009  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
template <class T> T _abs(T x){return (x>0)? x:-x;}  
template <class T> T _max(T x,T y){return (x>y)? x:y;}  
template <class T> T _min(T x,T y){return (x<y)? x:y;}  
template <class T> void getmax(T &x,T y){x= (x>y)? x:y;}  
template <class T> void getmin(T &x,T y){x= (x!=-1 && x<y)? x:y;}  
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}  
int TS,cas=1;  
const int M=200+5;  
int n,m;  
int a[M];  
char maze[M][M];  
  
struct sap{  
    typedef int type;  
    struct edge{  
        int to,next;  
        type flow;  
    }edg[999999];  
    int n,m;  
    int g[M],cur[M],pre[M];  
    int dis[M],gap[M];  
    int q[M],head,tail;  
    void init(int _n){n=_n,m=0,clr_all(g,-1);}  
    void insert(int u,int v,type f,type c=0){  
        edg[m].to=v,edg[m].flow=f,edg[m].next=g[u],g[u]=m++;  
        edg[m].to=u,edg[m].flow=0,edg[m].next=g[v],g[v]=m++;  
    }  
    bool bfs(int s,int t){  
        clr(gap,0,n),clr(dis,-1,n);  
        gap[dis[t]=0]++,dis[s]=-1;  
        for(q[head=tail=0]=t;head<=tail;){  
            int u=q[head++];  
            for(int i=g[u];i!=-1;i=edg[i].next){  
                edge& e=edg[i],ee=edg[i^1];  
                if(dis[e.to]==-1 && ee.flow>0){  
                    gap[dis[e.to]=dis[u]+1]++;  
                    q[++tail]=e.to;  
                }  
            }  
        }  
        return dis[s]!=-1;  
    }  
    type maxFlow(int s,int t){  
        if(!bfs(s,t)) return 0;  
        type res=0,a;  
        int i;  
        for(i=0;i<n;i++) cur[i]=g[i];  
        pre[s]=s,cur[s]=g[s],cur[t]=g[t];  
        for(int u=s;dis[s]<n;){  
            if(u==t){  
                for(a=-1;u!=s;u=pre[u])  
                    getmin(a,edg[cur[pre[u]]].flow);  
                for(u=t;u!=s;u=pre[u]){  
                    edg[cur[pre[u]]].flow-=a;  
                    edg[cur[pre[u]]^1].flow+=a;  
                }  
                res+=a;  
            }  
            bool ok=0;  
            for(i=cur[u];i!=-1;i=edg[i].next){  
                edge& e=edg[i];  
                if(dis[u]==dis[e.to]+1 && e.flow>0){  
                    cur[u]=i,pre[e.to]=u,u=e.to;  
                    ok=1;break;  
                }  
            }  
            if(ok) continue;  
            int mindis=n-1;  
            for(i=g[u];i!=-1;i=edg[i].next){  
                edge& e=edg[i];  
                if(mindis>dis[e.to] && e.flow>0)  
                    mindis=dis[e.to],cur[u]=i;  
            }  
            if(--gap[dis[u]]==0) break;  
            gap[dis[u]=mindis+1]++,u=pre[u];  
    &nb
补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,