CF网络流练习
2024-09-05 05:57:56
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+, 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 ;
}
struct edge {
int v,w,next;
} e[N];
int head[N], dep[N], cur[N], cnt=;
queue<int> Q;
void add(int u, int v, int w) {
e[++cnt] = {v,w,head[u]};
head[u] = cnt;
e[++cnt] = {u,,head[v]};
head[v] = cnt;
}
int bfs() {
REP(i,,T) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=,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]+&&e[i].w) {
dep[e[i].v]=dep[u]+;
Q.push(e[i].v);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].v]==dep[x]+&&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^].w += flow;
if (used==w) break;
}
}
}
return used;
}
int dinic() {
int ans = ;
while (bfs()) ans+=dfs(S,INF);
return ans;
} int main() {
scanf("%d", &n), S = n+, T = S+;
REP(i,,n) {
int k, t;
scanf("%d", &k);
while (k--) {
scanf("%d", &t);
g[i].pb(t+n);
g[t+n].pb(i);
}
}
REP(i,,n) ++clk, dfs(i);
int sum = ;
REP(i,,n) {
int t;
scanf("%d", &t);
t = -t;
if (t>=) add(S,i,t),sum+=t;
else add(i,T,-t);
}
REP(i,,n) for (int j:g[i]) add(i,f[j],INF);
printf("%d\n", dinic()-sum);
}
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+,S=N-,T=N-,INF=0x3f3f3f3f;
int n,m,cost,flow,b[N];
struct edge {
int to,next,w,v;
edge(int to=,int next=,int w=,int v=):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],cnt=;
queue<int> Q; int spfa() {
REP(i,,*b) dep[i]=-INF,vis[i]=;
dep[T]=-INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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] = ;
int used = ;
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^].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],,-v);
head[y] = cnt;
} int k,L[N],R[N],c[N],no[N];
int main() {
scanf("%d%d", &n, &k);
REP(i,,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+,b++*b),*b=unique(b+,b++*b)-b-;
REP(i,,n) {
L[i]=lower_bound(b+,b++*b,L[i])-b;
R[i]=lower_bound(b+,b++*b,R[i])-b;
}
add(S,,k,),add(*b,T,k,);
REP(i,,*b) add(i-,i,k,);
REP(i,,n) no[i]=cnt+,add(L[i],R[i],,c[i]);
dinic();
REP(i,,n) printf("%d ", !e[no[i]].w);
puts("");
}
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+,S=N-,T=N-,INF=0x3f3f3f3f;
int n,m,cost,flow,b[N];
struct edge {
int to,next,w,v;
edge(int to=,int next=,int w=,int v=):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],cnt=;
queue<int> Q; int spfa() {
REP(i,,n+) dep[i]=INF,vis[i]=;
dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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] = ;
int used = ;
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^].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],,-v);
head[y] = cnt;
} int f[N];
char s[N]; int main() {
scanf("%s%d", s+, &n);
m = strlen(s+);
REP(i,,m) ++f[s[i]];
int sum = ;
REP(i,'a','z') if (f[i]) {
add(n+i-'a'+,T,f[i],),sum+=f[i],f[i]=;
}
REP(i,,n) {
int x;
scanf("%s%d", s+, &x);
m = strlen(s+);
REP(i,,m) ++f[s[i]];
add(S,i,x,);
REP(j,'a','z') if (f[j]) add(i,n+j-'a'+,f[j],i);
REP(i,'a','z') f[i]=;
}
dinic();
if (flow!=sum) return puts("-1"),;
printf("%d\n", cost);
}
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+;
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,,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(),vis[n]=;
memset(ans,-,sizeof ans);
while (q.size()) {
int x = q.front(); q.pop();
vis[x] = ;
for (_ e:g[x]) {
if (e.id<) {
if (ans[-e.id]==-) ans[-e.id]=;
}
else if (ans[e.id]==-) ans[e.id]=;
if (!vis[e.to]) {
if (!(deg[e.to]-=*e.w)) {
q.push(e.to);
}
}
}
}
REP(i,,m) printf("%d\n",ans[i]);
}
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+, 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,,-w});
}
void mfmc(int S, int T) {
while () {
REP(i,,T) a[i]=INF,d[i]=1e15,inq[i]=;
q.push(S),d[S]=;
while (!q.empty()) {
int x=q.front(); q.pop();
inq[x] = ;
for (auto t:g[x]) {
auto e=E[t];
if (e.w>&&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]=;
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]^].w+=a[T];
}
mf+=a[T],mc+=a[T]*d[T];
}
} int x[N],y[N];
int main() {
scanf("%d", &n);
int S=*n+,T=S+;
REP(i,,n) {
scanf("%d%d",x+i,y+i);
add(S,i,,);
add(i+n,T,,);
}
REP(i,,n) REP(j,,n) if (y[i]>y[j]) {
add(i,j+n,,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
}
mfmc(S,T);
if (mf!=n-) return puts("-1"),;
printf("%.10lf\n",mc);
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n, m, g, a[N], b[N];
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
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,,head[v]);
head[v] = cnt;
}
int bfs() {
REP(i,,n+m) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
while (bfs()) ans+=dfs(S,INF);
return ans;
} int main() {
scanf("%d%d%d", &n, &m, &g);
REP(i,,n) scanf("%d",a+i);
REP(i,,n) scanf("%d",b+i);
REP(i,,n) {
if (a[i]) add(S,i,b[i]);
else add(i,T,b[i]);
}
int sum = ;
REP(i,,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\n",sum-dinic());
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n, m, flow, cost;
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),v(v),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
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,,-k,head[v]);
head[v] = cnt;
}
int spfa() {
REP(i,,n*m) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
Q.push(e[i].to);
}
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].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^].w+=w;
}
flow += w, cost += w*dep[T];
}
}
int a[][];
const int dx[]={,,-,};
const int dy[]={-,,,};
int ID(int x, int y) {
return (x-)*m+y;
}
int main() {
scanf("%d%d", &n, &m);
REP(i,,n) REP(j,,m) scanf("%d",a[i]+j);
REP(i,,n) REP(j,,m) {
if (i!=n) {
int x=ID(i,j),y=ID(i+,j);
if (i+j&) swap(x,y);
add(x,y,,a[i][j]!=a[i+][j]);
}
if (j!=m) {
int x=ID(i,j),y=ID(i,j+);
if (i+j&) swap(x,y);
add(x,y,,a[i][j]!=a[i][j+]);
}
if (i+j&) add(ID(i,j),T,,);
else add(S,ID(i,j),,);
}
EK();
printf("%d\n",cost);
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int n, m, flow, cost;
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
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,,-k,head[v]);
head[v] = cnt;
}
int spfa() {
REP(i,,n+m) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].w+=w;
}
flow += w, cost += w*dep[T];
}
}
int a[N], b[N], c[N];
char s[][]; int main() {
scanf("%d%d", &n, &m);
REP(i,,n) scanf("%s%d",s[i],a+i);
int sum = ;
REP(i,,m) scanf("%d",b+i),sum+=b[i];
REP(i,,m) add(S,i,,);
REP(i,,n) add(i+m,T,,);
REP(i,,m) REP(j,,n) {
if (s[j][]=='A') {
if (b[i]>=a[j]) add(i,j+m,,a[j]);
else add(i,j+m,,1e6);
}
else {
if (b[i]>a[j]) add(i,j+m,,b[i]);
else add(i,j+m,,1e6);
}
}
EK();
int ans = sum-cost;
REP(i,,n) if (s[i][]=='A') c[++*c]=a[i];
sort(b+,b++m,greater<int>());
sort(c+,c++*c);
int ret = ;
REP(i,,min(m,*c)) ret += max(,b[i]-c[i]);
printf("%d\n",max(ans,ret));
}
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+,INF=0x3f3f3f3f;
int n,m,cost,flow,S,T;
struct edge {
int to,next,w,v;
edge(int to=,int next=,int w=,int v=):to(to),next(next),w(w),v(v){}
} e[N];
int head[N],dep[N],vis[N],f[N],cnt=;
pii pre[N];
queue<int> Q; int spfa() {
REP(i,,n) f[i]=dep[i]=INF,vis[i]=;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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^].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],,-v);
head[y] = cnt;
} int a[][];
int main() {
scanf("%d%d", &n, &m);
S=,T=n;
REP(i,,n) REP(j,,n) {
scanf("%d", a[i]+j);
if (a[i][j]) add(i,j,a[i][j],);
}
EK();
REP(i,,n) REP(j,,n) {
if (a[i][j]) add(i,j,m,);
}
EK();
printf("%d\n", flow);
}
11. 434D
大意: $n$个数, 范围$[l,r]$, 第$i$个数若选$x$则有贡献$a_ix^2+b_ix+c$, 有$m$个限制$(u,v,d)$, 表示$x_u\le 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+, S = N-, T = N-, 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=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,tot) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,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,,n) scanf("%d%d%d",a+i,b+i,c+i);
int ma = -1e9;
REP(i,,n) {
scanf("%d%d", l+i, r+i);
REP(j,l[i],r[i]) ma=max(ma,f(i,j));
}
REP(i,,n) {
--l[i],++r[i];
add(S,ID(i,l[i]),INF);
REP(j,l[i]+,r[i]-) add(ID(i,j-),ID(i,j),-f(i,j));
add(ID(i,r[i]-),ID(i,r[i]),INF),add(ID(i,r[i]),T,INF);
}
REP(i,,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\n", -dinic());
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int flow, cost, k, n;
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,,*k) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-k,head[v]);
head[v] = cnt;
} int a[][],b[][],ans[N],ID[N];
char s[N],ss[N],t[N],val[N]; int main() {
scanf("%d%d", &n, &k);
REP(i,,min(,k)) ID[val[i]=i-+'a']=i;
REP(i,,k) ID[val[i]=i-+'A']=i;
scanf("%s%s",s+,ss+);
REP(i,,n) ++a[ID[s[i]]][ID[ss[i]]];
REP(i,,k) add(S,i,,),add(i+k,T,,);
REP(i,,k) REP(j,,k) b[i][j]=cnt+,add(i,j+k,,-a[i][j]);
EK();
printf("%d\n", -cost);
REP(i,,k) REP(j,,k) if (!e[b[i][j]].w) ans[i]=val[j];
REP(i,,k) putchar(ans[i]);puts("");
}
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=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;} const int N = 1e6+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n,m,tot;
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,tot) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,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,,mx) {
while (x%i==) x/=i,++v[i];
}
if (x>) ++v[x];
return v;
} int main() {
scanf("%d%d", &n, &m);
REP(i,,n) {
f[i]=fac(rd());
if (i&) 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,,m) {
int u=rd(),v=rd();
if (u&) 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\n", dinic());
}
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=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;} const int N = 1e6+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n;
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,n) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,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,,mx) if (!f[i]) {
for (int j=i*i; j<=n; j+=i) f[j] = ;
}
} int main() {
seive();
scanf("%d", &n);
REP(i,,n) {
if ((a[i]=rd())&) add(S,i,);
else add(i,T,);
}
REP(i,,n) if (a[i]&) REP(j,,n) if (a[j]&^) {
if (!f[a[i]+a[j]]) add(i,j,);
}
if (dinic()!=n) return puts("Impossible"),;
REP(i,,n) if (a[i]&) {
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,,n) vis[i] = ;
int cnt = ;
REP(i,,n) if (!vis[i]) {
++cnt;
int j = i;
while () {
vis[j] = ;
ans[cnt].pb(j);
if (vis[g[j][]]&&vis[g[j][]]) break;
if (vis[g[j][]]) j=g[j][];
else j=g[j][];
}
}
printf("%d\n", cnt);
REP(i,,cnt) {
printf("%d ", (int)ans[i].size());
for (int j:ans[i]) printf("%d ",j);
puts("");
}
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs(int n) {
REP(i,,n) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic(int n) {
int ans = ;
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,,head[v]);
head[v] = cnt;
} int n,m,x,y;
struct _ {int x,y,t;} h, a[N], b[N];
char s[][];
int v[][];
int ID(int x, int y) {
return (x-)*m+y;
}
const int dx[]={,,-,};
const int dy[]={-,,,};
int chk(ll tot) {
cnt = ;
REP(i,,*x+*n*m) head[i]=;
head[S]=head[T]=;
queue<_> q;
REP(i,,x) {
add(S,i,);
q.push({a[i].x,a[i].y,});
memset(v,,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] = ;
REP(k,,) {
int xx=u.x+dx[k],yy=u.y+dy[k];
if (<=xx&&xx<=n&&<=yy&&yy<=m) {
q.push({xx,yy,u.t+});
}
}
}
REP(j,,n) REP(k,,m) if (v[j][k]) add(i,ID(j,k)+*x,);
}
REP(i,,x) {
add(i+x,T,);
q.push({b[i].x,b[i].y,});
memset(v,,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] = ;
REP(k,,) {
int xx=u.x+dx[k],yy=u.y+dy[k];
if (<=xx&&xx<=n&&<=yy&&yy<=m) {
q.push({xx,yy,u.t+});
}
}
}
REP(j,,n) REP(k,,m) if (v[j][k]) add(ID(j,k)+*x+n*m,i+x,);
}
REP(i,,n) REP(j,,m) if (s[i][j]!='#') add(ID(i,j)+*x,ID(i,j)+*x+n*m,);
return dinic(*x+*n*m)==x;
} int main() {
scanf("%d%d%d%d", &n, &m, &x, &y);
if (abs(x-y)!=) return puts("-1"),;
REP(i,,n) scanf("%s",s[i]+);
scanf("%d%d%d",&h.x,&h.y,&h.t);
REP(i,,x) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
REP(i,,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=,r=1e18,ans=-;
while (l<=r) {
ll mid = (l+r)/;
if (chk(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%lld\n", ans);
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n, m, s1, s2, ans[][];
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,*n) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,head[v]);
head[v] = cnt;
}
int main() {
scanf("%d%d", &n, &m);
REP(i,,n) {
int t;
scanf("%d", &t);
s1 += t;
add(S,i,t),add(i,i+n,INF);
}
REP(i,,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"),;
puts("YES");
REP(i,,n) {
for (int j=head[i]; j; j=e[j].next) {
if (<=e[j].to-n&&e[j].to-n<=n) ans[i][e[j].to-n] = e[j^].w;
}
}
REP(i,,n) {
REP(j,,n) printf("%d ",ans[i][j]);
puts("");
}
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n, b, q, a[N];
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,*b+) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,head[v]);
head[v] = cnt;
} int main() {
scanf("%d%d%d", &n, &b, &q);
REP(i,,b) {
a[i] = -;
add(i,*b++i%,);
}
REP(i,,) add(*b++i%,T,n/);
REP(i,,q) {
int x, y;
scanf("%d%d", &x, &y);
if (a[x]!=-&&a[x]!=y) return puts("unfair"),;
a[x] = y;
}
if (a[b]!=-&&a[b]!=n) return puts("unfair"),;
a[b] = n;
int tot = , pre = ;
REP(i,,b) if (a[i]!=-) {
if (a[i]<tot) return puts("unfair"),;
if (a[i]!=tot) {
add(S,i+b,a[i]-tot);
REP(j,pre+,i) add(i+b,j,);
}
tot = a[i], pre = i;
}
puts(dinic()==n?"fair":"unfair");
}
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-;
const int N = 1e6+, 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=,ll w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,n) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
ll dfs(int x, ll w) {
if (x==T) return w;
ll used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
ll dinic() {
ll ans = ;
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,,head[v]);
head[v] = cnt;
}
int chk(double w) {
w /= x;
if (fabs(w)<=eps) return ;
cnt = , S = , T = n;
REP(i,,n) head[i] = ;
REP(i,,m) add(a[i],b[i],c[i]/w);
return dinic()>=x;
} int main() {
scanf("%d%d%d", &n, &m, &x);
REP(i,,m) scanf("%d%d%d",a+i,b+i,c+i);
double l=,r=1e11,ans;
REP(i,,) {
double mid=(l+r)/;
if (chk(mid)) ans=mid,l=mid+eps;
else r=mid-eps;
}
printf("%.10000lf\n", ans);
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int flow, cost;
int n,m,x,w[N];
char s[],p[][];
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,,n+) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-k,head[v]);
head[v] = cnt;
} int main() {
scanf("%d%s",&n,s);
scanf("%d",&m);
REP(i,,m) scanf("%s%d",p[i],w+i);
scanf("%d",&x);
add(S,,x,);
REP(i,,n) add(i,i+,x,);
add(n+,T,x,);
REP(i,,m) {
int len = strlen(p[i]);
REP(j,,n-) {
if (strncmp(s+j,p[i],len)==) add(j+,j++len,,-w[i]);
}
}
EK();
printf("%d\n",-cost);
}
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+;
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-, T = N-, INF = 0x3f3f3f3f;
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,tot) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,head[v]);
head[v] = cnt;
}
} void get(int x, int y, _ e) {
if (dep[x]<dep[y]) return;
int sz = ;
for (int t=x; t!=y; t=fa[t].to) ++sz;
Dinic::add(Dinic::S,++tot,sz);
Dinic::add(tot,e.w,), vis[e.id] = ;
for (int t=x; t!=y; t=fa[t].to) {
Dinic::add(tot,fa[t].w,), vis[fa[t].id] = ;
}
}
void dfs(int x, int f) {
dep[x]=dep[f]+;
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,,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,);
}
dfs(,);
REP(i,,m) if (!vis[i]) Dinic::add(Dinic::S,w[i],);
printf("%d\n", Dinic::dinic());
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n;
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,n) dep[i]=INF,vis[i]=,cur[i]=head[i];
REP(i,S-,T) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,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-] = x;
return s[x] = --now;
} int main() {
ID("S"),ID("M"),ID("L"),ID("XL"),ID("XXL"),ID("XXXL");
REP(i,,) {
int t;
scanf("%d", &t);
if (t) add(S-i,T,t);
}
scanf("%d", &n);
REP(i,,n) {
string t;
cin>>t;
for (auto &c:t) if (c==',') c=' ';
stringstream ss(t);
while (ss>>t) add(i,ID(t),);
add(S,i,);
}
if (dinic()!=n) return puts("NO"),;
puts("YES");
REP(i,,n) {
for (int j=head[i]; j; j=e[j].next) {
if (!e[j].w) cout<<val[e[j].to]<<endl;
}
}
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int n, p, s, flow, cost;
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
vector<int> g[N];
queue<int> Q;
int spfa() {
REP(i,,n) f[i]=dep[i]=INF,vis[i]=;
REP(i,S-,T) f[i]=dep[i]=INF,vis[i]=;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-k,head[v]);
head[v] = cnt;
} int main() {
scanf("%d%d%d", &n, &p, &s);
REP(i,,n) {
int t;
scanf("%d", &t);
add(S,i,,);
add(i,S-,,-t);
}
REP(i,,n) {
int t;
scanf("%d", &t);
add(i,S-,,-t);
}
add(S-,T,p,),add(S-,T,s,);
EK();
REP(i,,n) {
for (int j(head[i]); j; j=e[j].next) {
if (!e[j].w) g[e[j].to].push_back(i);
}
}
printf("%d\n", -cost);
for (int i:g[S-]) printf("%d ",i);puts("");
for (int i:g[S-]) printf("%d ",i);puts("");
}
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+, INF = 0x3f3f3f3f;
const int X = N-, Y = N-, S = N-, T = N-;
const double eps = 1e-;
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=,int w=,double v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N],x[N],y[N];
vector<int> g[N];
queue<int> Q;
int spfa() {
REP(i,,n) f[i]=dep[i]=INF,vis[i]=;
REP(i,N-,N-) f[i]=dep[i]=INF,vis[i]=;
dep[S]=,Q.push(S);
while (Q.size()) {
int p = Q.front(); Q.pop();
vis[p] = ;
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]=;
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]^].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,,-k,head[v]);
head[v] = cnt;
} int main() {
scanf("%d%d%d", &n, &a, &b);
REP(i,,n) scanf("%lf", u+i);
REP(i,,n) scanf("%lf", v+i);
REP(i,,n) {
add(S,i,,);
add(S,i,,u[i]*v[i]);
add(i,X,,-u[i]);
add(i,Y,,-v[i]);
}
add(X,T,a,),add(Y,T,b,);
EK();
printf("%.5lf\n", -cost);
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int n, k, flow, cost, a[N], c[N], lst[N];
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,,n) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-k,head[v]);
head[v] = cnt;
} int main() {
scanf("%d%d", &n, &k);
REP(i,,n) scanf("%d",a+i);
REP(i,,n) scanf("%d",c+i);
REP(i,,n) {
add(S,i,,c[a[i]]);
add(i,i+n,,);
add(i+n,T,,);
if (i!=) add(i-,i,k-,);
if (lst[a[i]]) add(i-,lst[a[i]]+n,,-c[a[i]]);
lst[a[i]] = i;
}
EK();
printf("%d\n", cost);
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int n, k, v[N];
struct _ {int p,c,l;} a[N];
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,n) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,head[v]);
head[v] = cnt;
} void seive(int n) {
int mx = sqrt(n+0.5);
REP(i,,mx) if (!v[i]) {
for (int j=i*i; j<=n; j+=i) v[j]=;
}
} int chk(int n) {
cnt = ;
REP(i,,n) head[i] = ;
REP(i,S,T) head[i] = ;
REP(i,,n) if ((a[i].c&)&&a[i].c>) REP(j,,n) {
if (!v[a[i].c+a[j].c]) add(i,j,INF);
}
REP(i,,n) if (a[i].c==) {
REP(j,,n) if (i!=j) {
if (a[j].c==) a[j].p=;
else if (!v[+a[j].c]) add(i,j,INF);
}
}
int sum = ;
REP(i,,n) {
sum += a[i].p;
if (a[i].c&) 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,,n) scanf("%d%d%d",&a[i].p,&a[i].c,&a[i].l);
sort(a+,a++n,[](_ a,_ b){return a.l<b.l||a.l==b.l&&a.p>b.p;});
int l=,r=n,ans=-;
while (l<=r) {
int mid=(l+r)/;
if (chk(mid)) ans=mid,r=mid-;
else l=mid+;
}
if (ans==-) return puts("-1"),;
printf("%d\n", a[ans].l);
}
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+, S = N-, T = N-, INF = 0x3f3f3f3f;
int V,E,n,k,a[N];
int dis[][];
struct edge {
int to,w,next;
edge(int to=,int w=,int next=):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=;
queue<int> Q;
int bfs() {
REP(i,,n+V) dep[i]=INF,vis[i]=,cur[i]=head[i];
dep[S]=INF,vis[S]=,cur[S]=head[S];
dep[T]=INF,vis[T]=,cur[T]=head[T];
dep[S]=,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]+&&e[i].w) {
dep[e[i].to]=dep[u]+;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = ;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+&&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^].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = ;
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,,head[v]);
head[v] = cnt;
} int chk(int x) {
cnt = ;
REP(i,,n+V) head[i] = ;
REP(i,S,T) head[i] = ;
REP(i,,n) REP(j,,V) {
if (dis[a[i]][j]<=x) add(i,j+n,);
}
REP(i,,n) add(S,i,);
REP(i,,V) add(i+n,T,);
return dinic()>=k;
} int main() {
scanf("%d%d%d%d", &V, &E, &n, &k);
REP(i,,n) scanf("%d",a+i);
memset(dis,0x3f,sizeof dis);
REP(i,,V) dis[i][i]=;
REP(i,,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,,V)REP(i,,V)REP(j,,V) {
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int l=,r=,ans=-;
while (l<=r) {
int mid=(l+r)/;
if (chk(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n", ans);
}
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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int n, tot, q, flow, cost;
int L[N], R[N];
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,,tot) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-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,,n) L[i]=,R[i]=n;
REP(i,,q) {
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if (op==) {
REP(j,l,r) L[j]=max(L[j],x);
}
else {
REP(j,l,r) R[j]=min(R[j],x);
}
}
REP(i,,n) {
if (L[i]>R[i]) return puts("-1"),;
add(S,ID(n+,i),,);
REP(j,L[i],R[i]) {
add(ID(n+,i),ID(i,j),,);
add(ID(i,j),ID(n+,j),,);
}
}
REP(i,,n) REP(j,,n) add(ID(n+,i),T,,*j-);
EK();
printf("%d\n", cost);
}
41. 884F
大意: 定义一个长为$n$的串$s$为反回文串, 当且仅当对于$1\le i\le n$有$s[i]!=s[n-i+1]$. 给定串$s$, 求将$s$重排为一个反回文串$t$, 对于$1\le i\le 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+, INF = 0x3f3f3f3f, S = N-, T = N-;
int n, tot, flow, cost, b[N], c[N];
char s[N];
struct edge {
int to,w,v,next;
edge(int to=,int w=,int v=,int next=):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,,tot) f[i]=dep[i]=INF,vis[i]=;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = ;
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]=;
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]^].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,,-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+);
REP(i,,n) ++c[s[i]];
REP(i,,n) scanf("%d",b+i);
REP(i,'a','z') add(S,ID(-,i),c[i],);
REP(i,,n) REP(j,'a','z') {
add(ID(-,j),ID(i,j),,s[i]==j?-b[i]:);
}
REP(i,,n/) {
REP(j,'a','z') {
add(ID(i,j),ID(i+n,j),,);
add(ID(n-i+,j),ID(i+n,j),,);
add(ID(i+n,j),ID(i,),,);
}
add(ID(i,),T,,);
}
EK();
printf("%d\n", -cost);
}
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
最新文章
- Eclipse自动补全设置
- Web跨域问题总结
- 用css画出三角形【转】
- 去掉安卓中activity的标题栏
- bzoj 2330: [SCOI2011]糖果
- 解决wamp mysql数据库出现乱码的问题。
- hadoop浅尝 第一个hadoop程序
- MFC解决Static控件背景透明时文本覆盖重影
- 自己动手搭建苹果推送Push服务器
- JQuery版评分控件
- leetcode First Bad Version（二分查找）
- myeclipse取消js校验
- devexpress entity framework 与 asp.net mvc的坑
- 腾讯云+校园扶持计划是bug还是福利
- Android APP开发入门教程-Button
- Dynamics 365的系统作业实体记录增长太快怎么回事?
- VS中，添加完Web引用(WebServer引用/Web服务引用)，写代码时引用不到
- 亚像素Sub Pixel
- [转]slf4j 与log4j 日志管理
- C#中POST数据和接收的几种方式