CF网络流练习

1. 103E

大意: 给定$n$个集合, 满足对于任意的$k$, 任意$k$个集合的并集都不少于$k$. 要求选出$k$个集合$(k> 0)$, 使得并恰好等于$k$, 输出最少花费.

Hall定理: 二分图的$X$部到$Y$部有完美匹配等价于$X$中任意$k$个点与$Y$中至少$k$个点相邻.

所有集合为$X$部, 每个数为$Y$部, 集合向所含数连边, 那么一定存在完美匹配. 假设求出一组匹配, 数字$i$对应集合$C_i$, 那么最终若选取集合$A_i$, 则$A_i$中所有数字$x$对应的集合$C_x$一定也要选, 把权值取负就转化为最大权闭合子图模型. 对于最大权闭合子图问题, 源点连所有正权点, 容量为该点权值, 所有负权点连汇点, 容量为该点权值的绝对值, 其余边与原图一样, 容量为无穷, 求出源点到汇点的最小割, 那么答案为正权和-最小割, 与源点间的割的含义为不选择该点, 与汇点间的割的含义为选择该点.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;

const int N = 1e6+10, INF = 0x3f3f3f3f;
int n, S, T, clk, f[N], vis[N];
vector<int> g[N];
int dfs(int x) {
    for (int y:g[x]) if (vis[y]!=clk) {
        vis[y] = clk;
        if (!f[y]||dfs(f[y])) return f[y]=x;
    }
    return 0;
}
struct edge {
    int v,w,next;
} e[N];
int head[N], dep[N], cur[N], cnt=1;
queue<int> Q;
void add(int u, int v, int w) {
    e[++cnt] = {v,w,head[u]};
    head[u] = cnt;
    e[++cnt] = {u,0,head[v]};
    head[v] = cnt;
}
int bfs() {
    REP(i,1,T) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].v]>dep[u]+1&&e[i].w) {
                dep[e[i].v]=dep[u]+1;
                Q.push(e[i].v);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].v]==dep[x]+1&&e[i].w) {
            int flow = dfs(e[i].v,min(w-used,e[i].w));
            if (flow) {
                used += flow;
                e[i].w -= flow;
                e[i^1].w += flow;
                if (used==w) break;
            }
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}


int main() {
    scanf("%d", &n), S = n+1, T = S+1;
    REP(i,1,n) {
        int k, t;
        scanf("%d", &k);
        while (k--) {
            scanf("%d", &t);
            g[i].pb(t+n);
            g[t+n].pb(i);
        }
    }
    REP(i,1,n) ++clk, dfs(i);
    int sum = 0;
    REP(i,1,n) {
        int t;
        scanf("%d", &t);
        t = -t;
        if (t>=0) add(S,i,t),sum+=t;
        else add(i,T,-t);
    }
    REP(i,1,n) for (int j:g[i]) add(i,f[j],INF);
    printf("%d
", dinic()-sum);
}

View Code

2. 164C

大意: $k$台机器, $n$个任务, 任务$i$开始时间$s_i$, 持续时间$t_i$, 获利$c_i$, 每台机器可以处理任何任务, 没处理完不能切换, 求完成哪些任务收益最大.

最大$k$重区间集问题, 时间离散化, 每个时间向下一个时间连容量$k$, 花费$0$, 任务$i$起点向终点连容量$1$, 花费$c_i$, 求出最大费用最大流即可.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 5e4+10,S=N-2,T=N-1,INF=0x3f3f3f3f;
int n,m,cost,flow,b[N];
struct edge {
    int to,next,w,v;
    edge(int to=0,int next=0,int w=0,int v=0):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],cnt=1;
queue<int> Q;

int spfa() {
    REP(i,1,*b) dep[i]=-INF,vis[i]=0;
    dep[T]=-INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (e[i].w&&dep[e[i].to]<dep[u]+e[i].v) {
                dep[e[i].to]=dep[u]+e[i].v;
                if (!vis[e[i].to]) { 
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=-INF;
}
int dfs(int x, int w) {
    if (x==T) {
        cost = cost+w*dep[T];
        flow += w;
        return w;
    }
    vis[x] = 1;
    int used = 0;
    for (int i=head[x]; i; i=e[i].next) {
        if (!vis[e[i].to]&&dep[e[i].to]==dep[x]+e[i].v&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) {
                used += f;
                e[i].w -= f;
                e[i^1].w += f;
                if(used==w) break;
            }
        }
    }
    return used;
}
void dinic(){
    while(spfa()) dfs(S,INF);
}
void add(int x,int y,int k,int v) {
    e[++cnt] = edge(y,head[x],k,v);
    head[x] = cnt;
    e[++cnt] = edge(x,head[y],0,-v);
    head[y] = cnt;
}

int k,L[N],R[N],c[N],no[N];
int main() {
    scanf("%d%d", &n, &k);
    REP(i,1,n) {
        int s,t;
        scanf("%d%d%d",&s,&t,c+i);
        b[++*b]=L[i]=s;
        b[++*b]=R[i]=s+t;
    }
    sort(b+1,b+1+*b),*b=unique(b+1,b+1+*b)-b-1;
    REP(i,1,n) { 
        L[i]=lower_bound(b+1,b+1+*b,L[i])-b;
        R[i]=lower_bound(b+1,b+1+*b,R[i])-b;
    }
    add(S,1,k,0),add(*b,T,k,0);
    REP(i,2,*b) add(i-1,i,k,0);
    REP(i,1,n) no[i]=cnt+1,add(L[i],R[i],1,c[i]);
    dinic();
    REP(i,1,n) printf("%d ", !e[no[i]].w);
    puts("");
}

View Code

3. 237E

大意: 给定字符串$t$, 给定$n$个子串, 第$i$个子串$s_i$最多可以选出$a_i$个字符, 每个字符花费为$i$, 求组成字符串$t$的最少花费.

裸的费用流, 源点向子串$i$连容量$a_i$, 费用$0$, $i$向每个字符$x$连容量$cnt_s[x]$, 费用$i$, 最后每个字符$x$向汇点连容量$cnt_t[x]$, 费用0. 求最小费用即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 5e4+10,S=N-2,T=N-1,INF=0x3f3f3f3f;
int n,m,cost,flow,b[N];
struct edge {
    int to,next,w,v;
    edge(int to=0,int next=0,int w=0,int v=0):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],cnt=1;
queue<int> Q;

int spfa() {
    REP(i,1,n+30) dep[i]=INF,vis[i]=0;
    dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (e[i].w&&dep[e[i].to]>dep[u]+e[i].v) {
                dep[e[i].to]=dep[u]+e[i].v;
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) {
        cost = cost+w*dep[T];
        flow += w;
        return w;
    }
    vis[x] = 1;
    int used = 0;
    for (int i=head[x]; i; i=e[i].next) {
        if (!vis[e[i].to]&&dep[e[i].to]==dep[x]+e[i].v&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) {
                used += f;
                e[i].w -= f;
                e[i^1].w += f;
                if(used==w) break;
            }
        }
    }
    return used;
}
void dinic(){
    while(spfa()) dfs(S,INF);
}
void add(int x,int y,int k,int v) {
    e[++cnt] = edge(y,head[x],k,v);
    head[x] = cnt;
    e[++cnt] = edge(x,head[y],0,-v);
    head[y] = cnt;
}

int f[N];
char s[N];

int main() {
    scanf("%s%d", s+1, &n);
    m = strlen(s+1);
    REP(i,1,m) ++f[s[i]];
    int sum = 0;
    REP(i,'a','z') if (f[i]) { 
        add(n+i-'a'+1,T,f[i],0),sum+=f[i],f[i]=0;
    }
    REP(i,1,n) {
        int x;
        scanf("%s%d", s+1, &x);
        m = strlen(s+1);
        REP(i,1,m) ++f[s[i]];
        add(S,i,x,0);
        REP(j,'a','z') if (f[j]) add(i,n+j-'a'+1,f[j],i);
        REP(i,'a','z') f[i]=0;
    }
    dinic();
    if (flow!=sum) return puts("-1"),0;
    printf("%d
", cost);
}

View Code

4. 269C

大意:给定无向图, 求将边定向, 使它成为一个$1$到$n$的流.

拓扑排序即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;


const int N = 1e6+10;
int n,m,deg[N],ans[N],vis[N];
struct _ {int to,w,id;};
vector<_> g[N];

int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,m) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb({v,w,i});
        g[v].pb({u,w,-i});
        deg[u]+=w,deg[v]+=w;
    }
    queue<int> q;
    q.push(1),vis[n]=1;
    memset(ans,-1,sizeof ans);
    while (q.size()) {
        int x = q.front(); q.pop();
        vis[x] = 1;
        for (_ e:g[x]) { 
            if (e.id<0) {
                if (ans[-e.id]==-1) ans[-e.id]=1;
            }
            else if (ans[e.id]==-1) ans[e.id]=0;
            if (!vis[e.to]) {
                if (!(deg[e.to]-=2*e.w)) { 
                    q.push(e.to);
                }
            }
        }
    }
    REP(i,1,m) printf("%d
",ans[i]);
}

View Code

5. 277E

大意: 给定$n$个平面点, $y$值大的可以向$y$值小的连有向边, 求一棵边权和最小的有根二叉树.

每个点入度1, 出度不超过2, 建图跑费用流即可.

#include <iostream>
#include <cstdio>
#include <queue>
#include <math.h>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;

const int N = 1e5+10, INF = 0x3f3f3f3f;
int n, m, k;
struct _ {int from,to,w;double f;};
vector<_> E;
vector<int> g[N];
int a[N], pre[N], inq[N];
double d[N];
int mf;
double mc;
queue<int> q;
void add(int x, int y, int c, double w) {
    g[x].pb(E.size());
    E.pb({x,y,c,w});
    g[y].pb(E.size());
    E.pb({y,x,0,-w});
}
void mfmc(int S, int T) {
    while (1) {
        REP(i,1,T) a[i]=INF,d[i]=1e15,inq[i]=0;
        q.push(S),d[S]=0;
        while (!q.empty()) {
            int x=q.front(); q.pop();
            inq[x] = 0;
            for (auto t:g[x]) {
                auto e=E[t];
                if (e.w>0&&d[e.to]>d[x]+e.f) {
                    d[e.to]=d[x]+e.f;
                    pre[e.to]=t;
                    a[e.to]=min(a[x],e.w);
                    if (!inq[e.to]) {
                        inq[e.to]=1;
                        q.push(e.to);
                    }
                }
            }
        }
        if (a[T]==INF) break;
        for (int u=T;u!=S;u=E[pre[u]].from) {
            E[pre[u]].w-=a[T];
            E[pre[u]^1].w+=a[T];
        }
        mf+=a[T],mc+=a[T]*d[T];
    }
}

int x[N],y[N];
int main() {
    scanf("%d", &n);
    int S=2*n+1,T=S+1;
    REP(i,1,n) { 
        scanf("%d%d",x+i,y+i);
        add(S,i,2,0);
        add(i+n,T,1,0);
    }
    REP(i,1,n) REP(j,1,n) if (y[i]>y[j]) { 
        add(i,j+n,1,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
    }
    mfmc(S,T);
    if (mf!=n-1) return puts("-1"),0;
    printf("%.10lf
",mc);
}

View Code

6. 311E

大意: $n$个点, 颜色黑或白, 翻转第$i$个点的颜色花费$v_i$, $m$个需求, 要求一些点全白或全黑, 满足则有一定收益. 有些特殊需求若不满足则要花费$g$, 求最大收益.

最大权闭合子图问题, 最大收益转为总收益减去最小割. $S$连黑点和黑需求, 白点和白需求连$T$, 再对每个需求关系连一下边即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, m, g, a[N], b[N];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}
int bfs() {
    REP(i,1,n+m) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}

int main() {
    scanf("%d%d%d", &n, &m, &g);
    REP(i,1,n) scanf("%d",a+i);
    REP(i,1,n) scanf("%d",b+i);
    REP(i,1,n) {
        if (a[i]) add(S,i,b[i]);
        else add(i,T,b[i]);
    }
    int sum = 0;
    REP(i,1,m) {
        int c,w,k,t,f;
        scanf("%d%d%d",&c,&w,&k);
        sum += w;
        while (k--) {
            scanf("%d", &t);
            if (c) add(i+n,t,INF);
            else add(t,i+n,INF);
        }
        scanf("%d", &f);
        if (f) f = g;
        if (c) add(S,i+n,f+w);
        else add(i+n,T,f+w);
    }
    printf("%d
",sum-dinic());
}

View Code

7. 316C

大意: 给定$n*m$矩阵, $n*m$为偶数, $[1,frac{nm}{2}]$每个数均出现$2$次, 求最少交换数使得相同数字相邻.

二分图最佳完美匹配, 每个点向相邻格子连边, 同色连费用0, 异色连费用1, 求出费用最小的完美匹配即为答案

#include <iostream>
#include <queue>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, m, flow, cost;
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),v(v),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
pair<int,int> pre[N];
queue<int> Q;
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}
int spfa() {
    REP(i,1,n*m) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=pair<int,int>(u,i);
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u].first) {
            e[pre[u].second].w-=w;
            e[pre[u].second^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
int a[99][99];
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
int ID(int x, int y) {
    return (x-1)*m+y;
}
int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) REP(j,1,m) scanf("%d",a[i]+j);
    REP(i,1,n) REP(j,1,m) {
        if (i!=n) {
            int x=ID(i,j),y=ID(i+1,j);
            if (i+j&1) swap(x,y);
            add(x,y,1,a[i][j]!=a[i+1][j]);
        }
        if (j!=m) {
            int x=ID(i,j),y=ID(i,j+1);
            if (i+j&1) swap(x,y);
            add(x,y,1,a[i][j]!=a[i][j+1]);
        }
        if (i+j&1) add(ID(i,j),T,1,0);
        else add(S,ID(i,j),1,0);
    }
    EK();
    printf("%d
",cost);
}

View Code

8. 321B

大意: 对手$n$只怪, 你有$m$只怪, 现在是你的回合. 对面怪全有嘲讽, 分为攻击怪和防御怪. 若你攻击对面攻击怪, 要满足你怪的能力不少于对面, 攻击后对面怪死亡, 对英雄伤害为能力差. 若你攻击对面防御怪, 要满足你怪的能力大于对面, 攻击后对面怪死亡, 对英雄伤害$0$. 若对面没怪可以直接攻击对面英雄, 伤害为你的怪的能力值. 求英雄造成的最大伤害.

不攻击英雄的情况贪心判掉. 攻击英雄的情况, 显然是一个最大带权匹配问题, 用费用流或者$KM$即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, m, flow, cost;
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}
int spfa() {
    REP(i,1,n+m) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
int a[N], b[N], c[N];
char s[110][10];

int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) scanf("%s%d",s[i],a+i);
    int sum = 0;
    REP(i,1,m) scanf("%d",b+i),sum+=b[i];
    REP(i,1,m) add(S,i,1,0);
    REP(i,1,n) add(i+m,T,1,0);
    REP(i,1,m) REP(j,1,n) {
        if (s[j][0]=='A') {
            if (b[i]>=a[j]) add(i,j+m,1,a[j]);
            else add(i,j+m,1,1e6);
        }
        else {
            if (b[i]>a[j]) add(i,j+m,1,b[i]);
            else add(i,j+m,1,1e6);
        }
    }
    EK();
    int ans = sum-cost;
    REP(i,1,n) if (s[i][0]=='A') c[++*c]=a[i];
    sort(b+1,b+1+m,greater<int>());
    sort(c+1,c+1+*c);
    int ret = 0;
    REP(i,1,min(m,*c)) ret += max(0,b[i]-c[i]);
    printf("%d
",max(ans,ret));
}

View Code

9. 343E

最小割树

10. 362E

大意: 给定$n$个点的网络图, 每次操作选一条边流量$+1$, 最多$k$次, 求最大流.

先求一次最大流, 然后对残量网络上每条边加一条容量$k$, 费用为$1$的边, 再跑一次费用流, 当费用达到$k$时停止.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef pair<int,int> pii;
const int N = 5e4+10,INF=0x3f3f3f3f;
int n,m,cost,flow,S,T;
struct edge {
    int to,next,w,v;
    edge(int to=0,int next=0,int w=0,int v=0):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],f[N],cnt=1;
pii pre[N];
queue<int> Q;

int spfa() {
    REP(i,1,n) f[i]=dep[i]=INF,vis[i]=0;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (e[i].w&&dep[e[i].to]>dep[u]+e[i].v) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=pii(u,i);
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) { 
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return cost+dep[T]<=m;
}
void EK(){
    while(spfa()) { 
        int w = f[T];
        if (cost+(long long)w*dep[T]>m) w = (m-cost)/dep[T];
        for (int u=T; u!=S; u=pre[u].first) {
            e[pre[u].second].w-=w;
            e[pre[u].second^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int x,int y,int k,int v) {
    e[++cnt] = edge(y,head[x],k,v);
    head[x] = cnt;
    e[++cnt] = edge(x,head[y],0,-v);
    head[y] = cnt;
}

int a[66][66];
int main() {
    scanf("%d%d", &n, &m);
    S=1,T=n;
    REP(i,1,n) REP(j,1,n) {
        scanf("%d", a[i]+j);
        if (a[i][j]) add(i,j,a[i][j],0);
    }
    EK();
    REP(i,1,n) REP(j,1,n) {
        if (a[i][j]) add(i,j,m,1);
    }
    EK();
    printf("%d
", flow);
}

View Code

11. 434D

大意: $n$个数, 范围$[l,r]$, 第$i$个数若选$x$则有贡献$a_ix^2+b_ix+c$, 有$m$个限制$(u,v,d)$, 表示$x_ule x_v+d$, 求贡献最大值.

最小割经典应用, 建图可以参照[HNOI2013]切糕. 本题是要求最大值, 流量取相反数, 转为最小, 但是因为流量不能有负数, 再全部增加一个值, 转为正.

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef pair<int,int> pii;

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int tot;
map<pii,int> mp;
int ID(int x, int y) {
    if (mp.count(pii(x,y))) return mp[pii(x,y)];
    return mp[pii(x,y)] = ++tot;
}
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,tot) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
} 

int n,m,a[N],b[N],c[N],l[N],r[N];
int f(int i, int x) {
    return a[i]*x*x+b[i]*x+c[i];
}

int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) scanf("%d%d%d",a+i,b+i,c+i);
    int ma = -1e9;
    REP(i,1,n) { 
        scanf("%d%d", l+i, r+i);
        REP(j,l[i],r[i]) ma=max(ma,f(i,j));
    }
    REP(i,1,n) {
        --l[i],++r[i];
        add(S,ID(i,l[i]),INF);
        REP(j,l[i]+1,r[i]-1) add(ID(i,j-1),ID(i,j),-f(i,j));
        add(ID(i,r[i]-1),ID(i,r[i]),INF),add(ID(i,r[i]),T,INF);
    }
    REP(i,1,m) { 
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        REP(j,l[v],r[v]) {
            int k = j+d;
            if (l[u]<=k&&k<=r[u]) { 
                add(ID(u,k),ID(v,j),INF);
            }
        }
    }
    printf("%d
", -dinic());
}

View Code

12. 491C

大意:给定两个长为$n$的串, 求改变第一个字符串的字母映射关系, 使得两个串对应位置相等的个数最大.

裸的最大带权匹配.

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 2e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int flow, cost, k, n;
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
    REP(i,1,2*k) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

int a[111][111],b[111][111],ans[N],ID[N];
char s[N],ss[N],t[N],val[N];

int main() {
    scanf("%d%d", &n, &k);
    REP(i,1,min(26,k)) ID[val[i]=i-1+'a']=i;
    REP(i,27,k) ID[val[i]=i-27+'A']=i;
    scanf("%s%s",s+1,ss+1);
    REP(i,1,n) ++a[ID[s[i]]][ID[ss[i]]];
    REP(i,1,k) add(S,i,1,0),add(i+k,T,1,0);
    REP(i,1,k) REP(j,1,k) b[i][j]=cnt+1,add(i,j+k,1,-a[i][j]);
    EK();
    printf("%d
", -cost);
    REP(i,1,k) REP(j,1,k) if (!e[b[i][j]].w) ans[i]=val[j];
    REP(i,1,k) putchar(ans[i]);puts("");
}

View Code

13. 498C

大意: 给定序列$a$, $m$个二元组$(x,y)$, 保证$x+y$为奇数, 每次操作任选一个二元组$(x,y)$, 选择一个$k>1$, 且$k$能整除$a_x$和$a_y$, 然后将$a_x,a_y$除以$k$, 求最多进行多少次操作.

裸的最大流.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n,m,tot;
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,tot) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}
map<int,int> f[N];
map<pii,int> mp;
int ID(int x, int y) {
    if (mp.count(pii(x,y))) return mp[pii(x,y)];
    return mp[pii(x,y)] = ++tot;
}
map<int,int> fac(int x) {
    int mx = sqrt(x+0.5);
    map<int,int> v;
    REP(i,2,mx) {
        while (x%i==0) x/=i,++v[i];
    }
    if (x>1) ++v[x];
    return v;
}

int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) { 
        f[i]=fac(rd());
        if (i&1) for (auto t:f[i]) add(ID(i,t.x),T,t.y);
        else for (auto t:f[i]) add(S,ID(i,t.x),t.y);
    }
    REP(i,1,m) {
        int u=rd(),v=rd();
        if (u&1) swap(u,v);
        for (auto t:f[u]) {
            if (f[v].count(t.x)) add(ID(u,t.x),ID(v,t.x),INF);
        }
    }
    printf("%d
", dinic());
}

View Code

14. 510E

大意: n只狐狸, 要求分成若干个环, 每个环的狐狸不少于三只, 相邻狐狸年龄和为素数.

年龄大于$1$, 那么两个数和为素数必然是一奇一偶, 奇偶分开建图跑最大流即可.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n;
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}

int f[N],a[N];
vector<int> g[N],ans[N];
void seive(int n) {
    int mx = sqrt(n+0.5);
    REP(i,2,mx) if (!f[i]) {
        for (int j=i*i; j<=n; j+=i) f[j] = 1;
    }
}

int main() {
    seive(20100);
    scanf("%d", &n);
    REP(i,1,n) { 
        if ((a[i]=rd())&1) add(S,i,2);
        else add(i,T,2);
    }
    REP(i,1,n) if (a[i]&1) REP(j,1,n) if (a[j]&1^1) {
        if (!f[a[i]+a[j]]) add(i,j,1);
    }
    if (dinic()!=n) return puts("Impossible"),0;
    REP(i,1,n) if (a[i]&1) {
        for (int t=head[i]; t; t=e[t].next) {
            if (!e[t].w&&e[t].to<=n) {
                g[i].pb(e[t].to);
                g[e[t].to].pb(i);
            }
        }
    }
    REP(i,1,n) vis[i] = 0;
    int cnt = 0;
    REP(i,1,n) if (!vis[i]) { 
        ++cnt;
        int j = i;
        while (1) {
            vis[j] = 1;
            ans[cnt].pb(j);
            if (vis[g[j][0]]&&vis[g[j][1]]) break;
            if (vis[g[j][0]]) j=g[j][1];
            else j=g[j][0];
        }
    }
    printf("%d
", cnt);
    REP(i,1,cnt) { 
        printf("%d ", (int)ans[i].size());
        for (int j:ans[i]) printf("%d ",j);
        puts("");
    }
}

View Code

15. 513F

大意: $n*m$的矩阵, 每个格子能住两个人, 给定每个人的位置以及移动速度, 求最短多少时间, 能使所有人都和一个异性分到一个房间.

二分答案, 建图, 看最大流是否满流.

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs(int n) {
    REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic(int n) {
    int ans = 0;
    while (bfs(n)) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
} 

int n,m,x,y;
struct _ {int x,y,t;} h, a[N], b[N];
char s[33][33];
int v[33][33];
int ID(int x, int y) {
    return (x-1)*m+y;
}
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
int chk(ll tot) {
    cnt = 1;
    REP(i,1,2*x+2*n*m) head[i]=0;
    head[S]=head[T]=0;
    queue<_> q;
    REP(i,1,x) { 
        add(S,i,1);
        q.push({a[i].x,a[i].y,0});
        memset(v,0,sizeof v);
        while (q.size()) {
            _ u = q.front(); q.pop();
            if (s[u.x][u.y]=='#'||v[u.x][u.y]) continue;
            if (a[i].t&&u.t>tot/a[i].t) continue;
            v[u.x][u.y] = 1;
            REP(k,0,3) {
                int xx=u.x+dx[k],yy=u.y+dy[k];
                if (1<=xx&&xx<=n&&1<=yy&&yy<=m) {
                    q.push({xx,yy,u.t+1});
                }
            }
        }
        REP(j,1,n) REP(k,1,m) if (v[j][k]) add(i,ID(j,k)+2*x,1);
    }
    REP(i,1,x) { 
        add(i+x,T,1);
        q.push({b[i].x,b[i].y,0});
        memset(v,0,sizeof v);
        while (q.size()) {
            _ u = q.front(); q.pop();
            if (s[u.x][u.y]=='#'||v[u.x][u.y]) continue;
            if (b[i].t&&u.t>tot/b[i].t) continue;
            v[u.x][u.y] = 1;
            REP(k,0,3) {
                int xx=u.x+dx[k],yy=u.y+dy[k];
                if (1<=xx&&xx<=n&&1<=yy&&yy<=m) {
                    q.push({xx,yy,u.t+1});
                }
            }
        }
        REP(j,1,n) REP(k,1,m) if (v[j][k]) add(ID(j,k)+2*x+n*m,i+x,1);
    }
    REP(i,1,n) REP(j,1,m) if (s[i][j]!='#') add(ID(i,j)+2*x,ID(i,j)+2*x+n*m,1);
    return dinic(2*x+2*n*m)==x;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    if (abs(x-y)!=1) return puts("-1"),0;
    REP(i,1,n) scanf("%s",s[i]+1);
    scanf("%d%d%d",&h.x,&h.y,&h.t);
    REP(i,1,x) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
    REP(i,1,y) scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].t);
    if (x>y) b[++y]=h;
    else a[++x]=h;
    ll l=0,r=1e18,ans=-1;
    while (l<=r) {
        ll mid = (l+r)/2;
        if (chk(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld
", ans);
}

View Code

16. 546E

大意: 给定无向图, 点$i$有$a_i$个士兵, 士兵只能移动不超过$1$, 求是否能使点$i$有$b_i$个士兵.

每个点拆成入点和出点, $S$连入点, 出点连$T$, 入点连接所有距离不超过$1$的出点, 判断能否满流即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, m, s1, s2, ans[111][111];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,2*n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
} 
int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) { 
        int t;
        scanf("%d", &t);
        s1 += t;
        add(S,i,t),add(i,i+n,INF);
    }
    REP(i,1,n) { 
        int t;
        scanf("%d", &t);
        s2 += t;
        add(i+n,T,t);
    }
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u,v+n,INF),add(v,u+n,INF);
    }
    if (s1!=s2||dinic()!=s1) return puts("NO"),0;
    puts("YES");
    REP(i,1,n) {
        for (int j=head[i]; j; j=e[j].next) {
            if (1<=e[j].to-n&&e[j].to-n<=n) ans[i][e[j].to-n] = e[j^1].w;
        }
    }
    REP(i,1,n) {
        REP(j,1,n) printf("%d ",ans[i][j]);
        puts("");
    }
}

View Code

17. 611H

18. 628F

大意: $n$元素集合, $n$被$5$整除, 模$5$后每种余数个数相同, 每个数范围在$[1,b]$内. 有$q$个限制$(x,y)$, 要求在$[1,x]$中恰好有$y$个数. 求是否能构造出该集合.

$q$个限制可以做一下差, 转化为$q$个不相交的区间$[l,r]$内恰有$y$个数, 然后就是很简单的建图了, 看能否满流即可.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, b, q, a[N];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,2*b+10) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}


int main() {
    scanf("%d%d%d", &n, &b, &q);
    REP(i,1,b) { 
        a[i] = -1;
        add(i,2*b+1+i%5,1);
    }
    REP(i,1,5) add(2*b+1+i%5,T,n/5);
    REP(i,1,q) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x]!=-1&&a[x]!=y) return puts("unfair"),0;
        a[x] = y;
    }
    if (a[b]!=-1&&a[b]!=n) return puts("unfair"),0;
    a[b] = n;
    int tot = 0, pre = 0;
    REP(i,1,b) if (a[i]!=-1) {
        if (a[i]<tot) return puts("unfair"),0;
        if (a[i]!=tot) {
            add(S,i+b,a[i]-tot);
            REP(j,pre+1,i) add(i+b,j,1);
        }
        tot = a[i], pre = i;
    }
    puts(dinic()==n?"fair":"unfair");
}

View Code

19. 653D

大意: 给定有向图, 有$x$只熊, 每只熊重量相同, 从节点$1$走到节点$n$, 每条路经过熊的总重量不能超过边权, 求每只熊重量最大值.

裸的最大流.

#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int n, m, x, S, T;
int a[N],b[N],c[N];
struct edge {
    int to;
    ll w;
    int next;
    edge(int to=0,ll w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
ll dfs(int x, ll w) {
    if (x==T) return w;
    ll used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
ll dinic() {
    ll ans = 0;
    while (bfs()) ans+=dfs(S,1e15);
    return ans;
}
void add(int u, int v, ll w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
} 
int chk(double w) {
    w /= x;
    if (fabs(w)<=eps) return 1;
    cnt = 1, S = 1, T = n;
    REP(i,1,n) head[i] = 0;
    REP(i,1,m) add(a[i],b[i],c[i]/w);
    return dinic()>=x;
}

int main() {
    scanf("%d%d%d", &n, &m, &x);
    REP(i,1,m) scanf("%d%d%d",a+i,b+i,c+i);
    double l=0,r=1e11,ans;
    REP(i,1,100) {
        double mid=(l+r)/2;
        if (chk(mid)) ans=mid,l=mid+eps;
        else r=mid-eps;
    }
    printf("%.10000lf
", ans);
}

View Code

20. 704D

大意: 给定平面上$n$个点, 每个点染为红色花费$r$, 蓝色花费$b$. 给定$m$个限制$(t,l,d)$, $t$为$1$表示直线$x=l$上红蓝点差不超过$d$, 否则是$y=l$上红蓝点差不超过$d$, 求最少花费.

21. 708D

22. 717G

大意: 给定一个串$s$, $n$个模式串, 模式串与主串匹配可以获得一定权值, 主串每个位置最多匹配$x$个模式串, 求最大权值.

裸的最长$k$重区间集, 费用流跑一下即可.

#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int flow, cost;
int n,m,x,w[N];
char s[510],p[110][510];
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
    REP(i,1,n+1) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

int main() {
    scanf("%d%s",&n,s);
    scanf("%d",&m);
    REP(i,1,m) scanf("%s%d",p[i],w+i);
    scanf("%d",&x);
    add(S,1,x,0);
    REP(i,1,n) add(i,i+1,x,0);
    add(n+1,T,x,0);
    REP(i,1,m) {
        int len = strlen(p[i]);
        REP(j,0,n-1) {
            if (strncmp(s+j,p[i],len)==0) add(j+1,j+1+len,1,-w[i]);
        }
    }
    EK();
    printf("%d
",-cost);
}

View Code

23. 720B

大意: 给定一个边仙人掌, 边有颜色, 求删除一些边, 使它变为树, 且剩余边颜色种类数最大.

非环边直接从$S$连向对应颜色, $S$向每个环连一条$size-1$的边, 每个环再向每种颜色对应连边, 每种颜色连向$T$, 求最大流即为答案.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;

const int N = 1e6+10;
int n, m, tot, dep[N], vis[N], u[N], v[N], w[N];
struct _ {int to,w,id;} fa[N];
vector<_> g[N];

namespace Dinic {
const int S = N-2, T = N-1, INF = 0x3f3f3f3f;
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,tot) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}
}

void get(int x, int y, _ e) {
    if (dep[x]<dep[y]) return;
    int sz = 0;
    for (int t=x; t!=y; t=fa[t].to) ++sz;
    Dinic::add(Dinic::S,++tot,sz);
    Dinic::add(tot,e.w,1), vis[e.id] = 1;
    for (int t=x; t!=y; t=fa[t].to) {
        Dinic::add(tot,fa[t].w,1), vis[fa[t].id] = 1;
    }
}
void dfs(int x, int f) {
    dep[x]=dep[f]+1;
    for (_ e:g[x]) if (e.to!=f) {
        int y = e.to;
        if (dep[y]) get(x,y,e);
        else fa[y]={x,e.w,e.id},dfs(y,x);
    }
}

int main() {
    scanf("%d%d", &n, &m), tot = m;
    REP(i,1,m) {
        scanf("%d%d%d", u+i, v+i, w+i);
        g[u[i]].pb({v[i],w[i],i}),g[v[i]].pb({u[i],w[i],i});
        Dinic::add(i,Dinic::T,1);
    }
    dfs(1,0);
    REP(i,1,m) if (!vis[i]) Dinic::add(Dinic::S,w[i],1);
    printf("%d
", Dinic::dinic());
}

View Code

24. 723E

大意: 给定无向图, 无重边自环, 不保证连通, 要求把每条边定向, 使得入度等于出度的点最多.

25. 724E

大意: 给定有向图, 所有编号小的点与编号大的点间有一条有向边, 每条边流量均为$c$, 点$i$产出为$p_i$, 最多购入$s_i$, 求所有城市总购入量的最大值.

26. 727D

大意: $6$种衬衫, 每个人有两种或一种需求, 问是否能满足所有人的需求.

裸最大流

#include <iostream>
#include <sstream>
#include <cstdio>
#include <map>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n;
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    REP(i,S-6,T) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}

map<string,int> s;
string val[N];
int now = S;

int ID(string x) {
    if (s.count(x)) return s[x];
    val[now-1] = x;
    return s[x] = --now;
}

int main() {
    ID("S"),ID("M"),ID("L"),ID("XL"),ID("XXL"),ID("XXXL");
    REP(i,1,6) {
        int t;
        scanf("%d", &t);
        if (t) add(S-i,T,t);
    }
    scanf("%d", &n);
    REP(i,1,n) {
        string t;
        cin>>t;
        for (auto &c:t) if (c==',') c=' ';
        stringstream ss(t);
        while (ss>>t) add(i,ID(t),1);
        add(S,i,1);
    }
    if (dinic()!=n) return puts("NO"),0;
    puts("YES");
    REP(i,1,n) {
        for (int j=head[i]; j; j=e[j].next) {
            if (!e[j].w) cout<<val[e[j].to]<<endl;
        }
    }
}

View Code

27. 730I

大意: $n$个人, 选出$p$个人的编程组, $s$个人的运动组, 每个组价值为编程能力和或运动能力和, 求总能力和的最大值.

裸费用流. 数据范围比较大, 试了一下EK+spfa还是可过, 也可以用堆模拟费用流.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, p, s, flow, cost;
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
vector<int> g[N];
queue<int> Q;
int spfa() {
    REP(i,1,n) f[i]=dep[i]=INF,vis[i]=0;
    REP(i,S-2,T) f[i]=dep[i]=INF,vis[i]=0;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}



int main() {
    scanf("%d%d%d", &n, &p, &s);
    REP(i,1,n) {
        int t;
        scanf("%d", &t);
        add(S,i,1,0);
        add(i,S-1,1,-t);
    }
    REP(i,1,n) {
        int t;
        scanf("%d", &t);
        add(i,S-2,1,-t);
    }
    add(S-1,T,p,0),add(S-2,T,s,0);
    EK();
    REP(i,1,n) {
        for (int j(head[i]); j; j=e[j].next) {
            if (!e[j].w) g[e[j].to].push_back(i);
        }
    }
    printf("%d
", -cost);
    for (int i:g[S-1]) printf("%d ",i);puts("");
    for (int i:g[S-2]) printf("%d ",i);puts("");
}

View Code

28. 736E

29. 739E

大意: $n$只精灵, $a$个普通球, $b$个高级球, 第$i$只精灵用普通球成功率$u_i$, 高级球$v_i$, 每只精灵同一种球最多用一次, 可以同时使用两种球, 求获得精灵期望最大值.

裸费用流, 同时扔两种球概率会减少$u_iv_i$, 从源点连一条流量$1$费用$0$, 和流量$1$费用$u_iv_i$的边即可, 这样一个点流量为$2$时, 费用一定会减去, 否则一定不会.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, INF = 0x3f3f3f3f;
const int X = N-4, Y = N-3, S = N-2, T = N-1;
const double eps = 1e-8;
int n, a, b, flow;
double cost, u[N], v[N], dep[N];
struct edge {
    int to,w;
    double v;
    int next;
    edge(int to=0,int w=0,double v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N],x[N],y[N];
vector<int> g[N];
queue<int> Q;
int spfa() {
    REP(i,1,n) f[i]=dep[i]=INF,vis[i]=0;
    REP(i,N-4,N-1) f[i]=dep[i]=INF,vis[i]=0;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int p = Q.front(); Q.pop();
        vis[p] = 0;
        for (int i=head[p]; i; i=e[i].next) if (e[i].w) {
            double dis = dep[p]+e[i].v;
            if (dep[e[i].to]>dis+eps) {
                dep[e[i].to]=dis;
                pre[e[i].to]=p,pre2[e[i].to]=i;
                f[e[i].to]=min(f[p],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, double k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

int main() {
    scanf("%d%d%d", &n, &a, &b);
    REP(i,1,n) scanf("%lf", u+i);
    REP(i,1,n) scanf("%lf", v+i);
    REP(i,1,n) {
        add(S,i,1,0);
        add(S,i,1,u[i]*v[i]);
        add(i,X,1,-u[i]);
        add(i,Y,1,-v[i]);
    }
    add(X,T,a,0),add(Y,T,b,0);
    EK();
    printf("%.5lf
", -cost);
}

View Code

30. 786E

大意: 给定树, 给定$m$个人行走路线, 要求要么每个人自带一条狗, 要么路线上每条边都放一条狗, 求最少要多少只狗.

31. 793G

大意: $n*n$棋盘, 每行每列只能有一个棋子, 有$q$个矩形区域不能放棋子, 求最多放多少棋子

32. 802C

大意: 书架容量为$k$, 有$n$种书, 第$i$种$c_i$元, $n$个人按顺序来借书, 借完立刻还回, 第$i$个人要第$a_i$种, 若此时书架无$a_i$, 则要花费$c_{a_i}$元买书, 若书架满了, 则要扔掉一本. 求最少花费.

费用流好题, 开$2n$个点, $S$向$i$连一条费用$c_{a_i}$的边, 表示第$i$天新买一本书, $i$向$i+n$连费用$0$的边, 表示当天借完直接扔掉, $i+n$向$T$连费用$0$的边, 表示借书. $i$向$i+1$连容量$k-1$的边, 表示前一天最多向后一天保留$k-1$本书, 假设$a_i$的上次出现位置为$lst_{a_i}$, $i-1$向$lst_{a_i}+n$连费用$-c_{a_i}$的边, 表示撤销掉第$lst_{a_i}$的扔书操作, 使该书一直保留到$i-1$天. 最后跑一次最小费用最大流即为答案.

#include <iostream>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, k, flow, cost, a[N], c[N], lst[N];
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
    REP(i,1,n) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

int main() {
    scanf("%d%d", &n, &k);
    REP(i,1,n) scanf("%d",a+i);
    REP(i,1,n) scanf("%d",c+i);
    REP(i,1,n) {
        add(S,i,1,c[a[i]]);
        add(i,i+n,1,0);
        add(i+n,T,1,0);
        if (i!=1) add(i-1,i,k-1,0);
        if (lst[a[i]]) add(i-1,lst[a[i]]+n,1,-c[a[i]]);
        lst[a[i]] = i;
    }
    EK();
    printf("%d
", cost);
}

View Code

33. 802O

大意: $n$道题, 第$i$天可以花费$a_i$准备一道题, 花费$b_i$打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印$k$道题.

中等难度就是裸的费用流, 困难用堆模拟费用流.

34. 808F

大意: $n$张牌, 第$i$张能力$p_i$,魔法值$c_i$,等级$l_i$, 要求组一套牌, 使得任意两张牌的魔法值和不为素数, 且能力和不少于$k$, 求所需牌的等级最大值的最小值.

先二分答案, 素数可以按奇偶分开转化为二分图最大带权独立集, 然后最小割即可. 需要特判一下$1$, 多个$1$时只取$p$值最大的那个.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n, k, v[N];
struct _ {int p,c,l;} a[N];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}

void seive(int n) {
    int mx = sqrt(n+0.5);
    REP(i,2,mx) if (!v[i]) {
        for (int j=i*i; j<=n; j+=i) v[j]=1;
    }
}

int chk(int n) {
    cnt = 1;
    REP(i,1,n) head[i] = 0;
    REP(i,S,T) head[i] = 0;
    REP(i,1,n) if ((a[i].c&1)&&a[i].c>1) REP(j,1,n) {
        if (!v[a[i].c+a[j].c]) add(i,j,INF);
    }
    REP(i,1,n) if (a[i].c==1) {
        REP(j,1,n) if (i!=j) { 
            if (a[j].c==1) a[j].p=0; 
            else if (!v[1+a[j].c]) add(i,j,INF);
        }
    }
    int sum = 0;
    REP(i,1,n) {
        sum += a[i].p;
        if (a[i].c&1) add(S,i,a[i].p);
        else add(i,T,a[i].p);
    }
    return sum-dinic()>=k;
}

int main() {
    seive(2e5);
    scanf("%d%d", &n, &k);
    REP(i,1,n) scanf("%d%d%d",&a[i].p,&a[i].c,&a[i].l);
    sort(a+1,a+1+n,[](_ a,_ b){return a.l<b.l||a.l==b.l&&a.p>b.p;});
    int l=1,r=n,ans=-1;
    while (l<=r) {
        int mid=(l+r)/2;
        if (chk(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if (ans==-1) return puts("-1"),0;
    printf("%d
", a[ans].l);
}

View Code

35. 813D & 818G

大意: 给定$n$元素序列, 求选出$4$个不相交的链, 链中相邻元素满足模7同余或差不超过$1$.

这题感觉建图没什么错但一直WA, 没调出来.

36. 843E

37. 848D

38. 847J

39. 852D

大意: 给定$V$节点$E$条边无向图, 给定$n$个队伍起始位置, 求最短多少时间$n$个队伍的结束位置不少于$k$.

先$floyd$求一下最短路, 然后二分答案看最大流是否超过$k$即可.

#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int V,E,n,k,a[N];
int dis[666][666];
struct edge {
    int to,w,next;
    edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
    REP(i,1,n+V) dep[i]=INF,vis[i]=0,cur[i]=head[i];
    dep[S]=INF,vis[S]=0,cur[S]=head[S];
    dep[T]=INF,vis[T]=0,cur[T]=head[T];
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+1&&e[i].w) {
                dep[e[i].to]=dep[u]+1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[T]!=INF;
}
int dfs(int x, int w) {
    if (x==T) return w;
    int used = 0;
    for (int i=cur[x]; i; i=e[i].next) {
        cur[x] = i;
        if (dep[e[i].to]==dep[x]+1&&e[i].w) {
            int f = dfs(e[i].to,min(w-used,e[i].w));
            if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
            if (used==w) break;
        }
    }
    return used;
}
int dinic() {
    int ans = 0;
    while (bfs()) ans+=dfs(S,INF);
    return ans;
}
void add(int u, int v, int w) {
    e[++cnt] = edge(v,w,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,head[v]);
    head[v] = cnt;
}

int chk(int x) {
    cnt = 1;
    REP(i,1,n+V) head[i] = 0;
    REP(i,S,T) head[i] = 0;
    REP(i,1,n) REP(j,1,V) { 
        if (dis[a[i]][j]<=x) add(i,j+n,1);
    }
    REP(i,1,n) add(S,i,1);
    REP(i,1,V) add(i+n,T,1);
    return dinic()>=k;
}

int main() {
    scanf("%d%d%d%d", &V, &E, &n, &k);
    REP(i,1,n) scanf("%d",a+i);
    memset(dis,0x3f,sizeof dis);
    REP(i,1,V) dis[i][i]=0;
    REP(i,1,E) {
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        dis[a][b]=dis[b][a]=min(dis[a][b],t);
    }
    REP(k,1,V)REP(i,1,V)REP(j,1,V) {
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    }
    int l=0,r=1731311,ans=-1;
    while (l<=r) {
        int mid=(l+r)/2;
        if (chk(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d
", ans);
}

View Code

40. 863F

大意: $n$元素序列, 每个元素取值范围$[1,n]$, 有$q$个限制$(t,l,r,x)$, 表示$[l,r]$内的元素$le x$或$ge x$, 定义$cnt_i$为元素$i$的出现次数, 求$sum cnt_i^2$的最小值.

费用流水题, 贡献为平方可以拆成$n$条流量为$1$, 费用为$1,3,5,7...$的边.

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef pair<int,int> pii;

const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, tot, q, flow, cost;
int L[N], R[N];
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
    REP(i,1,tot) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

map<pii,int> mp;
int ID(int x, int y) {
    if (mp.count(pii(x,y))) return mp[pii(x,y)];
    return mp[pii(x,y)] = ++tot;
}


int main() {
    scanf("%d%d", &n, &q);
    REP(i,1,n) L[i]=1,R[i]=n;
    REP(i,1,q) {
        int op,l,r,x;
        scanf("%d%d%d%d",&op,&l,&r,&x);
        if (op==1) {
            REP(j,l,r) L[j]=max(L[j],x);
        }
        else {
            REP(j,l,r) R[j]=min(R[j],x);
        }
    }
    REP(i,1,n) {
        if (L[i]>R[i]) return puts("-1"),0;
        add(S,ID(n+2,i),1,0);
        REP(j,L[i],R[i]) {
            add(ID(n+2,i),ID(i,j),1,0);
            add(ID(i,j),ID(n+1,j),1,0);
        }
    }
    REP(i,1,n) REP(j,1,n) add(ID(n+1,i),T,1,2*j-1);
    EK();
    printf("%d
", cost);
}

View Code

41. 884F

大意: 定义一个长为$n$的串$s$为反回文串, 当且仅当对于$1le ile n$有$s[i]!=s[n-i+1]$. 给定串$s$, 求将$s$重排为一个反回文串$t$, 对于$1le ile n$, 若$s[i]=t[i]$, 则得分$b[i]$, 求最大得分值.

挺不错的费用流题, 也可以贪心做.

统计一下每个字符的出现次数$c_i$, 从$S$向字符$x$连$c_x$. 每个位置$i$拆成$26$个点, 从字符$x$连向每个点, 若$s[i]=x$则加一个费用$-b_i$. 然后就是处理反回文的限制, 对于每对限制$(i,n-i+1)$, 再新开$26$个点, $i$和$n-i+1$分别向新开的点连容量$1$, 最后再开个点限制两边流量和为$2$即可. 这样建图的话实际上会导致一个错误: 每对限制$(i,n-i+1)$, 可能取了$i$两个, 而$n-i+1$没有取到. 但是思考一下很容易发现这样并不影响最终结果.

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef pair<int,int> pii;
const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, tot, flow, cost, b[N], c[N];
char s[N];
struct edge {
    int to,w,v,next;
    edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
    REP(i,1,tot) f[i]=dep[i]=INF,vis[i]=0;
    f[S]=dep[S]=f[T]=dep[T]=INF;
    dep[S]=0,Q.push(S);
    while (Q.size()) {
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i=head[u]; i; i=e[i].next) {
            if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
                dep[e[i].to]=dep[u]+e[i].v;
                pre[e[i].to]=u,pre2[e[i].to]=i;
                f[e[i].to]=min(f[u],e[i].w);
                if (!vis[e[i].to]) {
                    vis[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
        }
    }
    return dep[T]!=INF;
}
void EK(){
    while(spfa()) {
        int w = f[T];
        for (int u=T; u!=S; u=pre[u]) {
            e[pre2[u]].w-=w;
            e[pre2[u]^1].w+=w;
        }
        flow += w, cost += w*dep[T];
    }
}
void add(int u, int v, int w, int k) {
    e[++cnt] = edge(v,w,k,head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u,0,-k,head[v]);
    head[v] = cnt;
}

map<pii,int> mp;
int ID(int x, int y) {
    if (mp.count(pii(x,y))) return mp[pii(x,y)];
    return mp[pii(x,y)] = ++tot;
}

int main() {
    scanf("%d%s", &n, s+1);
    REP(i,1,n) ++c[s[i]];
    REP(i,1,n) scanf("%d",b+i);
    REP(i,'a','z') add(S,ID(-1,i),c[i],0);
    REP(i,1,n) REP(j,'a','z') {
        add(ID(-1,j),ID(i,j),1,s[i]==j?-b[i]:0);
    }
    REP(i,1,n/2) {
        REP(j,'a','z') {
            add(ID(i,j),ID(i+n,j),1,0);
            add(ID(n-i+1,j),ID(i+n,j),1,0);
            add(ID(i+n,j),ID(i,1),1,0);
        }
        add(ID(i,1),T,2,0);
    }
    EK();
    printf("%d
", -cost);
}

View Code

42. 903G

大意:两个n元素集合$A$, $B$, $A_i$与$A_{i+1}$连一条有向边, $B_i$与$B_{i+1}$连一条有向边, 给定$m$条从$A_i$连向$B_j$的有向边, 每次询问修改$A_x->A_{x+1}$的边权, 求$A_1$->$B_n$的最大流.

43. 925F

44. 965D

大意: 河宽$w$, 青蛙每步能跳不超过$l$, 有$w-1$块石头, 石头每踩一次就会消失, 求最大过河青蛙数.

45. 976F

大意: 给定二分图, 对于$k in [0,minDegree]$, 输出最小$k$覆盖.

46. 1009G

47. 1016D

大意: 有一个$nm$矩阵, 给定每行每列异或和, 求是否存在. 若存在输出一个方案.

1045A

1054F

1061E

1070I

1107F

1119B

1139E

1146G