列表

详情

NC237204. 拯救萝莉(hard version)

描述

本题有对应的easy version，区别仅在于easy version多一个额外限制条件，见输入描述，保证easy version的测试用例集是hard version的子集。
注意hard version中有额外样例。
邪恶的魔王抓走了所有的小萝莉，并且把她们关在了N个城堡中，不过好消息是，清楚姐姐现在已经占领了1号城堡，并且在城堡中训练一些士（群）兵（友）来作战。

城堡与城堡之间有M条单向运兵线路，清楚姐姐只能按照这些单向道路派兵攻打敌方城堡。
这N个城堡的分布结构呈一张有向无环图（DAG）的结构，并且保证从1号城堡出发可以通过单向道路到达其他N-1个城堡中。

对于除了1号城堡以外的每一个城堡，都被大魔王控制，每一座城堡有三个属性：防御力D，敌人总数A，以及人口数P。

清楚姐姐在任意时刻都可以进行如下几个操作
  • 移动：清楚姐姐可以命令自己的士兵按照城堡间的单向道路移动，前提是单向道路两端的城堡均已被清楚姐姐控制或为中立状态。
  • 攻击：清楚姐姐可以选择一个敌方控制的目标城堡，以及若干个己方已控制且可直接通过运兵路线攻击目标的城堡发动一次攻击，攻击所需的兵力由这若干个城堡随意分配，每次进攻时，若干个己方城堡用于进攻的兵力总和S不得少于D，我方士兵与敌方死战。
                    若则战斗结束后目标城堡的敌人总数变为A-S，我方参与本场战斗的士兵全部战死。
                    若则战斗结束后目标城堡中我方士兵与敌方士兵全部阵亡，城堡处于无人的中立状态。
                    若则战斗结束后目标城堡中我方士兵剩余S-A，全歼敌人，可以直接进行“占领”操作。
  • 占领：当我方战斗结束全歼敌人且至少有1人存活，或者往中立城堡派出1个士兵后，可以进行占领，占领后该城堡变为我方控制状态，且最多可以招募P人成为我方士兵，新招募的士兵初始位置位于该占领的城堡。对于已经占领的城堡，可以将所有士兵都调走，即使所有士兵都离开也不会转化为中立状态。
  • 招募：除了一开始的1号城堡以外，每一个我方控制的城堡都可以最多招募不多于该城堡人口上限P的士兵。
为了拯救小萝莉，清楚姐姐需要占领其余N-1个城堡。
现在智乃想知道，清楚姐姐一开始在1号城堡中训练多少群友才能达成目标。

有向无环图oi-wiki：https://oi-wiki.org/graph/dag/
牛客竞赛图论课程：https://ac.nowcoder.com/courses/cover/live/740
不会做说明该买课了（

输入描述

第一行输入两个正整数表示城堡的数目N以及单向运兵路线的数目M。
接下来N-1行，每行输入三个非负整数表示从2号城堡到N号城堡的防御力D，敌人总数A，以及人口数P。
接下来M行，每行输入两个正整数表示一条单向运兵线路。
输入保证这些运兵线路构成一个DAG图，且从1号城堡可到达所有城堡。

输出描述

仅一行一个整数，表示清楚姐姐一开始在1号城堡中训练多少群友才能达成目标。

示例1

输入: 

3 2
0 1 99
100 100 0
1 2
2 3

输出: 

3

说明:

一开始训练3名群友，派它们攻击2号城堡。2号城堡的防御力为0，所以可以派3名群友直接进攻该城堡。
战斗结束后，在2号城堡内我方剩余2名士兵，占领2号城堡并招募99人，此时城堡内有101人。
最后派101人攻击3号城堡，在3号城堡内我方剩余1名士兵，占领该城堡获得胜利。

示例2

输入: 

2 1
100 1 0
1 2

输出: 

100

说明:

城堡的防御力为100，需要至少100人同时进攻才能攻打城堡。

示例3

输入: 

2 1
1 100 0
1 2

输出: 

101

说明:

注意至少需要1人存活才能占领城堡。

示例4

输入: 

10 9
5 7 6
0 9 5
9 2 2
8 7 9
10 2 0
4 3 5
4 10 8
9 8 8
1 2 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出: 

14

示例5

输入: 

4 4
60 50 100
50 60 100
210 210 0
1 2
1 3
2 4
3 4

输出: 

121

说明:

注意可以同时选中多个已经占领的城堡，合力进攻。
一开始在1号城堡招募121名群友，派60人攻打2号城堡，派61人攻打3号城堡。
攻打之后立刻进行招募，此时2号城堡内有110人，3号城堡内有101人、
选中2号，3号城堡合力共211人进攻4号城堡成功占领所有城堡。

示例6

输入: 

12 15
93474 10128 65752
65221 6983 41034
82452 34722 48764
21423 41519 59398
760 34788 24645
51178 9985 15211
52050 76240 64792
20318 16102 23494
90614 48972 68565
4694 22617 70520
76983 90440 76132
1 2
8 9
1 4
1 10
1 3
1 4
4 5
1 10
5 11
11 12
4 6
6 7
7 8
1 9
3 6

输出: 

331761

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 11ms, 内存消耗: 604K, 提交时间: 2022-10-20 11:47:18 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std ;

using ll = long long ;

const int N = 20000,M = 2 * N ;
const int INF = 1e9 ;

int n,m,S,T ;
int h[N],e[M],f[M],ne[M],idx; 
int q[N],dep[N],cur[N] ;  // cur[]是为了使用当前弧优化，起名dep也是为了避免和dfs的d重名

void add(int a,int b,int c){  // 加边
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
    e[idx] = a,f[idx] = 0 ,ne[idx]= h[b],h[b] = idx ++ ;
}

bool bfs(){  // bfs
    int hh = 0 ,tt = 0 ;
    for(int i = 0 ; i <= T ; i++){
        cur[i] = h[i] ;
        dep[i] = INF ;
    }
    q[0] = S,dep[S] = 0 ;

    while(hh <= tt){
        int t = q[hh++] ;

        for(int i = h[t] ; ~ i ; i = ne[i]){
            int j = e[i] ;
            if(dep[j] == INF && f[i]){
                dep[j] = dep[t] + 1 ;
                q[++tt] = j;
            }
        }
    }

    if(dep[T] == INF) return 0;
    return 1 ;
}

int dfs(int u,int d){  
    if(u == T) return d;
    int used = 0 ;  // 以及用过的流量
    for(int i = cur[u] ; ~ i ; i = ne[i]){  // 当前弧优化
        cur[u] = i ;
        int j = e[i] ;
        if(dep[j] == dep[u] + 1 && f[i]){
            int nd ;
            if(nd = dfs(j,min(f[i],d-used))){
                f[i] -= nd ;
                f[i^1] += nd ;
                used += nd ;
                if(used == d) break ;  // 当用过的等于当前点，返回
            }
        }
    }
    return used ;
}

ll dinic(){
    ll res = 0,t ;
    while(bfs()) while(t = dfs(S,INF)) res += t ;
    return res ;
}

int main(){
    scanf("%d%d",&n,&m) ;
    S = 0,T = 2 * n + 1 ;
    fill(h,h+T+1,-1) ;
    ll ans = 0 ;
    for(int i = 2 ; i <= n ; i ++){
        int d,a,p ;
        scanf("%d%d%d",&d,&a,&p) ;
        int tot = max(a+1,d) ;
        add(S,i,tot - a + p) ;
        add(i+n,T,tot) ;
        ans += tot ;
    }
    
    for(int i = 1 ; i <= m ; i ++){
        int a,b ;
        scanf("%d%d",&a,&b) ;
        add(a+n,b+n,INF) ;
        add(a,b+n,INF) ;
    }

    printf("%lld\n",ans - dinic()) ;
    return 0 ;
}

C++ 解法, 执行用时: 12ms, 内存消耗: 948K, 提交时间: 2022-06-02 09:46:18 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, M = (N + 125003) * 2, INF = 2147483647;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N], A[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    int sum=0;
    scanf("%d%d", &n, &m);
    S = 0, T = 2*n + 1;
    memset(h, -1, sizeof h);
    int x,a,b;
    for(int i=2;i<=n;i++)
    {
        cin>>x>>a>>b;
        add(S,i,max(1,x-a)+b);
        add(i+n,T,max(x,a+1));
        sum+=max(x,a+1);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        add(a+n,b+n,1e9);
        add(a,b+n,1e9);
    }
    cout<<sum-dinic()<<endl;
    return 0;
}

上一题

© 2025 nowcoder.com