P3701 主主树 题解

· · 题解

题目传送门：P3701 主主树。

思路

这道题一看就是用网络最大流来求解。

接下来我们考虑如何建图。

  1. 建立一个超级源点 S，S 向 byx 的每个人连接流量为人物寿命的边。
  2. 建立一个超级汇点 T，诗乃酱的每个人向 T 连接流量为人物寿命的边。
  3. 根据题目中的关系，如果 byx 的第 i 个人，可以打败诗乃酱的第 j 个人，那么 i 和 j 连一条，流量为 1 的边。

注意：由于题目中说，当 J 的寿命为 0 时，同一棵树上的 YYY 可以为他增加 1 秒的寿命，因此 J 的寿命是本身寿命加上 YYY 个数。

最后我们的答案就为 \min(\text{最大流},m)，因为最多比赛 m 场。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h[1234567],e[1234567],f[1234567],nx[1234567],cur[1234567],d[1234567],cnt,s,t,n,m;
pair<string,int> bb[1234567],ss[1234567];
#define a first
#define b second
void add(int u,int v,int w){
    e[cnt]=v,f[cnt]=w,nx[cnt]=h[u],h[u]=cnt++;
    e[cnt]=u,f[cnt]=0,nx[cnt]=h[v],h[v]=cnt++;
}
bool bfs(){
    for (int i=0;i<=t;i++) d[i]=-1;
    d[s]=0;
    cur[s]=h[s];
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for (int i=h[u];~i;i=nx[i]){
            int v=e[i],w=f[i];
            if (d[v]==-1&&w){
                d[v]=d[u]+1;
                cur[v]=h[v];
                if (v==t) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int find(int u,int limit){
    if (u==t) return limit;
    int flow=0;
    for (int i=cur[u];~i&&flow<limit;i=nx[i]){
        int v=e[i],w=f[i];
        cur[u]=i;
        if (d[v]==d[u]+1&&w){
            int x=find(v,min(w,limit-flow));
            if (!x) d[v]=-1;
            flow+=x;
            f[i]-=x;
            f[i^1]+=x;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(s,1e9)) r+=flow;
    return r;
}
int check(string x,string y,int i,int j){
    if (x=="YYY"&&y=="HK") add(i,j+n,1);
    if (x=="YYY"&&y=="J") add(i,j+n,1);
    if (x=="E"&&y=="YYY") add(i,j+n,1);
    if (x=="E"&&y=="J") add(i,j+n,1);
    if (x=="J"&&y=="HK") add(i,j+n,1);
    if (x=="J"&&y=="W") add(i,j+n,1);
    if (x=="W"&&y=="YYY") add(i,j+n,1);
    if (x=="W"&&y=="E") add(i,j+n,1);
    if (x=="HK"&&y=="W") add(i,j+n,1);
    if (x=="HK"&&y=="E") add(i,j+n,1);
}
main(){
    cin>>n>>m;
    int cntb=0,cnts=0;
    for (int i=1;i<=n;i++){
        cin>>bb[i].a;
        if (bb[i].a=="YYY") cntb++;
    } 
    for (int i=1;i<=n;i++){
        cin>>ss[i].a;
        if (ss[i].a=="YYY") cnts++;
    } 
    for (int i=1;i<=n;i++){
        cin>>bb[i].b;
        if (bb[i].a=="J") bb[i].b+=cntb;
    }
    for (int i=1;i<=n;i++){
        cin>>ss[i].b;
        if (ss[i].a=="J") ss[i].b+=cnts;
    }
    s=0,t=n+n+1;
    for (int i=0;i<=t;i++) h[i]=-1;
    for (int i=1;i<=n;i++) add(s,i,bb[i].b),add(i+n,t,ss[i].b);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            check(bb[i].a,ss[j].a,i,j);
    cout <<min(dinic(),m);
    return 0;
}