只会抄题解
网络流练习
听说loli要考网络流专场？Emmmm……那就练一练吧 反正这玩意挺有意思的
luogu2598 狼和羊的故事
这属于题意杀吧……
这题我光看题看了30min？！主要是比较疑惑为0的区域到底是都能去还是都不能去，自己理解了半天还是没悟出来(明明是一直在听歌 古风电音有毒)
然后问了一下asia大佬，结果这才是一系列翻车的开始
asia大佬信心满满的跟我说这个0不用管它，狼和羊都不能去，这妥妥套路题啊！原点连狼汇点连羊inf，狼和相邻的羊连个1不就得了！我TM一拍大腿，有道理啊，然后又手胡了30min的最小割，又TM一拍大腿，这不对劲啊！
这么建图直接把狼和相邻的羊之间有多少条边统计出来不就得了，跑什么网络流啊！
之后两个人一合计，又胡出了什么羊羊相连inf之类的操作……结果发现也不对，连起来没啥意义啊！
asia大佬自觉翻车，又回去看了看题，告诉我0是两个都能去的……
我去……
这样的话就出来建图了，源点与狼连接inf，狼和0和羊只要相邻就连1，但要注意狼节点只能把源点给的流往外流，羊节点只能汇集外面的流流到汇点，0和0之间要连双向为1的边，这样求最小割就能把狼和羊两个集合分开。
但是调了半天代码发现不过，最后终于发现是出了什么事情：
网络流建图的时候，一定要注意，对于一对正反边，加边的时候一定要一起加，不然增广的时候会出问题！
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define inc inline char
#define ini inline int
#define big 1e9
using namespace std;
int n,m,cnt,tot,ans,s,t=10001;
int a[101][101],dis[10010],head[100010],cur[100010],dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
queue<int> q;
struct node{
int next,to,dis;
}ljb[100010];
inv add_edge(int x,int y,int z){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].dis=z;
head[x]=cnt;
}
inv add(int x,int y,int z){
add_edge(x,y,z);
add_edge(y,x,0);
}
inc gc()
{
static char BUFF[1000000],*S=BUFF,*T=BUFF;
return S==T&&(T=(S=BUFF)+fread(BUFF,1,1000000,stdin),S==T)?EOF:*S++;
}
ini read()
{
char c;rint r=0,f=1;
c=gc();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=gc();
}
while (c>='0' && c<='9'){
r=r*10+(c^48);
c=gc();
}
return r*f;
}
inb bfs()
{
for (rint i=s;i<=t;i++) dis[i]=-1;
q.push(s);dis[s]=0;
while (!q.empty()){
rint x=q.front();q.pop();
for (rint i=head[x];i!=-1;i=ljb[i].next){
rint y=ljb[i].to;
if (dis[y]==-1 && ljb[i].dis>0){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
if (dis[t]>=0) return 1;
return 0;
}
ini dfs(int x,int low)
{
if (x==t) return low;
for (rint& i=cur[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==dis[x]+1 && ljb[i].dis>0){
rint flow=dfs(y,min(low,ljb[i].dis));
if (flow){
ljb[i].dis-=flow;
ljb[i^1].dis+=flow;
return flow;
}
}
}
return 0;
}
inb pd(int i,int j)
{
if (i>=1 && i<=n && j>=1 && j<=m) return 1;
return 0;
}
int main()
{
n=read();m=read();
for (rint i=1;i<=n;i++)
for (rint j=1;j<=m;j++)
a[i][j]=read();
for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
for (rint i=1;i<=n;i++)
for (rint j=1;j<=m;j++){
rint now=(i-1)*m+j;
if (a[i][j]==1) add(now,t,big);
else{
if (a[i][j]==2) add(s,now,big);
for (rint k=1;k<=4;k++){
rint x=i+dx[k],y=j+dy[k];
rint nowd=(x-1)*m+y;
if (a[x][y]!=2 && pd(x,y)) add(now,nowd,1);
}
}
}
while (bfs()){
for (rint i=s;i<=t;i++) cur[i]=head[i];
do{
tot=dfs(s,big);
ans+=tot;
}
while (tot);
}
printf("%d",ans);
}
luogu2053 修车
网络流好题
这道题也算搓了很久了……一直没有思路，只能怪我比较zz。
然后我发现我被题意杀了……要注意，不能一个人同时修好几辆车，也不能好几个人同一辆车，但是可以好几个人同时修好几辆分别不同的车。
要用到一个很骚的逆向思维。
我们把每个人拆成n个点，一共m乘n个，其中任意一个记为a[i,j]，也就是第i个人修的倒数第j辆车。这里要注意，这个倒数第j是相对于第i个人的，并不是总体上的倒数第j辆。我们再开n个点，其中任意一个记为k，也就是第k辆车。我们的原始数组，第i个人修第k辆车，记为b[i,k]。把a[i,j]和k一连，就是第i个人倒数第j个修车，修的是第k辆。因为这辆车是倒数第j个修，所以一共要有j辆车等待b[i,k]的时间才行。这样一来，j乘b[i,k]就表示这种情况要耗费多少时间。
我们把s连接n个表示顺序的点，流量1，费用0，这个好说。
然后就像刚才我们说的那样，这n个点中每个点k都要连接每个a[i,j]，流量1，费用为j*b[i,k]。
然后我们再把m*n个点连到汇点上，流量1，费用0。
代码
#include<iostream>
#include<cstdio>
#include<queue>
#define big 1e9
#define maxn 100000
using namespace std;
int dis[maxn],pre[maxn],flow[maxn],lst[maxn],head[maxn],n,m,cnt,ans,s,t,b[1001][1001];
bool vis[maxn];
queue<int> q;
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=(r<<3)+(r<<1)+(c^48);
c=getchar();
}
return r*f;
}
struct node{
int next,to,flow,dis;
}ljb[maxn];
void add_edge(int x,int y,int f,int c){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].flow=f;
ljb[cnt].dis=c;
head[x]=cnt;
}
void add(int x,int y,int f,int c){
add_edge(x,y,f,c);
add_edge(y,x,0,-c);
}
bool spfa(){
for (int i=s;i<=t;i++) dis[i]=big,flow[i]=big,pre[i]=-1,lst[i]=0,vis[i]=0;
q.push(s);dis[s]=0;vis[s]=1;pre[s]=0;
while (!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]>dis[x]+ljb[i].dis && ljb[i].flow>0){
dis[y]=dis[x]+ljb[i].dis;
flow[y]=min(flow[x],ljb[i].flow);
pre[y]=x;lst[y]=i;
if (!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
if (pre[t]!=-1) return 1;
return 0;
}
int main()
{
m=read();n=read();t=m*n+n+1;
for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
for (int k=1;k<=n;k++) add(s,m*n+k,1,0);
for (int k=1;k<=n;k++)
for (int i=1;i<=m;i++)
b[i][k]=read();
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
int now=(i-1)*n+j;
for (int k=1;k<=n;k++) add(m*n+k,now,1,j*b[i][k]);
add(now,t,1,0);
}
while (spfa()){
ans+=flow[t]*dis[t];
int now=t;
while (now){
ljb[lst[now]].flow-=flow[t];
ljb[lst[now]^1].flow+=flow[t];
now=pre[now];
}
}
printf("%.2lf",ans/(n*1.0));
}
[luogu2469 星际竞速]
虽小路径覆盖系列绝佳题目。
一开始看完题之后轻松搓出来一个图，源点连接每个点，费用为a[i]，然后各个点之间能到达的都连上，费用为边权，之后每个点连一波汇点。搓完这个图感觉怎么这么简单，不像SDOI的画风啊……就去看了一眼题解。
然后我就看见了最小路径覆盖这几个大字。靠。
我立马想到做那个题的时候一开始也是类似这样的建图，但是突然发现这样建图的话直接跑源点到自己到汇点一定是最大(这里就不详细说了，具体咋回事看下面的链接)。
先让我们回顾一下最小路径覆盖这个题。就是有一个图，要你找出能够覆盖所有的点的最少路径数，而且不能有两条路径有共同的顶点。我们仔细一想，这道星际竞速可不就是费用流版的最小路径覆盖？只不过不是求最小路径覆盖，而是求最大匹配数。
那么最小路径覆盖是怎么做的？我们先拆点，一个出点专门往外出发出边，一个入点专门接受边，源点向出点引一条边，入点向汇点引一条边。
正确性的证明可以这么想：因为流量是1，所以每个点只能到达汇点一次，可以满足只选一次。对于每一次增广，我们都只增广了两个点和一条边，也就是源点→出点→入点→汇点，(这里注意出点和入点不是一个点拆成的，是两个点分别的出点和入点)，而如果我们跑最小费用最大流的话，每次增广都是费用最小的，所以我们可以增广出花最小的费用可以选哪些边。
但是这个题还有跳跃操作。这个怎么搞？
其实只要我们想清楚，每次增广只是增广一条边而不是一条路径，一切就全都明了了。
先想想为什么要有跳跃这个操作？因为如果一个行星到另一个行星要花巨额的钱，但我们只需要经历所有的点而不是所有的边，所以就要跳跃。
这就非常巧妙了。我们可以用两个我们已经知道的事实来证明接下来的操作：
1.我们每次增广都只增广一条边
2.对于跳跃后到达的行星来说，它的上一站是谁对花费没有影响
所以我们可以直接从源点向每一个入点发出一条花费为a[i]的边。我们可以这么想，如果一个点从任何路径到达都不如跳跃到达，那么我们就走这条边，就相当于把这个点标记为跳跃到达。
如果你仔细看完上面的证明过程，应该就没有什么问题了。
建图：
源点→每个出点 流量1费用0
每个出点→能到达的入点 流量1费用为边权
每个入点→汇点 流量1费用0
源点→每个入点 流量1费用a[i]
代码
#include<iostream>
#include<cstdio>
#include<queue>
#define big (1000000000 + 10)
#define maxn (100000 + 10)
using namespace std;
int dis[maxn],flow[maxn],pre[maxn],lst[maxn],head[maxn];
int n,m,ans,cnt,s=0,t=2001;
bool vis[maxn];
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=(r*10)+(c^48);
c=getchar();
}
return r*f;
}
struct edge{
int next,to,flow,dis;
}ljb[maxn];
void add_edge(int x,int y,int f,int c){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].flow=f;
ljb[cnt].dis=c;
head[x]=cnt;
}
void add(int x,int y,int f,int c){
add_edge(x,y,f,c);
add_edge(y,x,0,-c);
}
queue<int> q;
bool spfa(){
for (int i=s;i<=t;i++) dis[i]=big,flow[i]=big,vis[i]=0,pre[i]=-1,lst[i]=0;
q.push(s);dis[s]=0;
while (!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]>dis[x]+ljb[i].dis && ljb[i].flow>0){
dis[y]=dis[x]+ljb[i].dis;
flow[y]=min(flow[x],ljb[i].flow);
pre[y]=x; lst[y]=i;
if (!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
if (pre[t]!=-1) return 1;
return 0;
}
int main(){
n=read();m=read();
for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
for (int i=1;i<=n;i++){
int x=read();
add(s,i,1,0);
add(i+800,t,1,0);
add(s,i+800,1,x);
}
for (int i=1;i<=m;i++){
int l=read(),r=read(),c=read();
if (l>r) swap(l,r);
add(l,r+800,1,c);
}
while (spfa()){
ans+=flow[t]*dis[t];
int now=t;
while (now!=s){
ljb[lst[now]].flow-=flow[t];
ljb[lst[now]^1].flow+=flow[t];
now=pre[now];
}
}
printf("%d",ans);
}
luogu3171 网络吞吐量
这题最难的不是读题么……
我先解释一下题目。这个题的意思就是说，我先给你个图，这个图有很多条最短路，你把这些最短路都给我标记上，然后我只在这些最短路的边上跑最大流。
但是要注意一点：跑最大流的时候边权只考虑吞吐量就行了(说白了就是拆点之后两点之间那条边)，其他的边都是inf，和之前spfa用的边权没什么关系。
所以说这个题其实就是考怎么把这些最短路标记出来。仔细一看就500个点，那直接只跑一遍最短路，然后从后往前一遍O(n)遍历艹出来就行了，不多解释。
代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
#define big (1000000000000000000ll +10)
#define maxn (250000 +10)
using namespace std;
int n,m,cnt,t=1001;
int head[maxn],cur[maxn];
long long dis[1010],ans,f[1010][1010],tot;
bool vis[1010],pd[1010][1010];
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=(r<<3)+(r<<1)+(c^48);
c=getchar();
}
return r*f;
}
struct node{
int next,to;ll dis;
}edge[maxn],ljb[maxn];
struct add{
void sp(int x,int y,ll z){
edge[++cnt].next=head[x];
edge[cnt].to=y;
edge[cnt].dis=z;
head[x]=cnt;
}
void wll(int x,int y,ll z){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].dis=z;
head[x]=cnt;
}
void di(int x,int y,ll z){
wll(x,y,z);
wll(y,x,0);
}
}a;
queue<int> q;
struct spfa{
void bfs(){
for (int i=1;i<=n;i++) dis[i]=big;
q.push(1);dis[1]=0;vis[1]=1;
while (!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for (int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if (dis[y]>dis[x]+edge[i].dis){
dis[y]=dis[x]+edge[i].dis;
if (!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
for (int i=1;i<=n;i++) vis[i]=0;
}
void dfs(int x){
vis[x]=1;
for (int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if (dis[y]+edge[i].dis==dis[x]){
pd[y][x]=pd[x][y]=1;
if (!vis[y] && y!=1) dfs(y);
}
}
}
}s;
struct dinic{
bool bfs(){
for (int i=1;i<=t;i++) dis[i]=-1;
q.push(1);dis[1]=0;
while (!q.empty()){
int x=q.front();q.pop();
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==-1 && ljb[i].dis>0){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
if (dis[t]!=-1) return 1;
return 0;
}
ll dfs(int x,ll low){
if (x==t) return low;
for (int& i=cur[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==dis[x]+1 && ljb[i].dis>0){
int flow=dfs(y,min(low,ljb[i].dis));
if (flow){
ljb[i].dis-=flow;
ljb[i^1].dis+=flow;
return flow;
}
}
}
return 0;
}
}d;
int main(){
n=read();m=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
f[i][j]=big;
for (int i=1;i<=m;i++){
int l=read(),r=read();ll k;scanf("%lld",&k);
f[l][r]=f[r][l]=min(f[l][r],k);
}
for (int i=2;i<=n;i++)
for (int j=1;j<=i-1;j++)
if (f[i][j]!=big){
a.sp(i,j,f[i][j]);
a.sp(j,i,f[i][j]);
}
s.bfs();
s.dfs(n);
for (int i=1;i<=t;i++) head[i]=-1;cnt=-1;
for (int i=1;i<=n;i++){
ll x;scanf("%lld",&x);
if (i!=1 && i!=n) a.di(i,i+500,x);
}
for (int i=2;i<=n;i++)
for (int j=1;j<=i-1;j++)
if (f[i][j]!=big && pd[i][j]){
if (i!=n) a.di(i+500,j,big);else a.di(i,j,big);
if (j!=1) a.di(j+500,i,big);else a.di(j,i,big);
}
a.di(n,t,big);
while (d.bfs()){
for (int i=1;i<=t;i++) cur[i]=head[i];
do{
tot=d.dfs(1,big);
ans+=tot;
}
while (tot);
}
printf("%lld",ans);
}
luogu2604 网络扩容
很妙的一道题 给出题者的脑洞打call
题目简单易懂，但是蛮有难度的……没看题解做出来自己也有那么一点意外。
这道题的第一问就是个板子。而第二问很明显要跑最小费用最大流——那么怎么把这个扩容的操作转化成最小费用最大流呢？
我们可以想到，每两个点在原边的基础上加一条有费用的边，而原边的费用设为0，就可以完成这样的转化。
但我们需要注意一点(也是昊哥提醒我我才发现)，如果要使得总流量扩容k，那么可能会有的边扩容不止k，大概那个图的形状是个“散射型”(什么鬼)，反正感性理解一下应该能明白。
所以我们就把新加的边流量设为inf，然后再把n点连一个汇点，流量maxflow+k，费用为0就可以了。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define big (1000000000 + 10)
#define maxn (100000 + 10)
using namespace std;
int dis[maxn],flow[maxn],pre[maxn],lst[maxn],head[maxn],cur[maxn];
int cnt,n,m,k,t,ans,tot,mflow;
bool vis[maxn];
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=(r*10)+(c^48);
c=getchar();
}
return r*f;
}
struct node{
int l,r,f,c;
}p[maxn];
struct edge{
int next,to,flow,dis;
}ljb[maxn];
void add_edge(int x,int y,int f,int c){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].flow=f;
ljb[cnt].dis=c;
head[x]=cnt;
}
void add(int x,int y,int f,int c){
add_edge(x,y,f,c);
add_edge(y,x,0,-c);
}
queue<int> q;
bool bfs(){
for (int i=1;i<=n;i++) dis[i]=-1;
q.push(1); dis[1]=0;
while (!q.empty()){
int x=q.front(); q.pop();
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==-1 && ljb[i].flow>0){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
if (dis[n]!=-1) return 1;
return 0;
}
int dfs(int x,int low){
if (x==n) return low;
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==dis[x]+1 && ljb[i].flow>0){
int flow=dfs(y,min(low,ljb[i].flow));
if (flow){
ljb[i].flow-=flow;
ljb[i^1].flow+=flow;
return flow;
}
}
}
return 0;
}
bool spfa(){
for (int i=1;i<=t;i++) dis[i]=big,flow[i]=big,vis[i]=0,pre[i]=-1,lst[i]=0;
q.push(1);dis[1]=0;
while (!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]>dis[x]+ljb[i].dis && ljb[i].flow>0){
dis[y]=dis[x]+ljb[i].dis;
flow[y]=min(flow[x],ljb[i].flow);
pre[y]=x; lst[y]=i;
if (!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
if (pre[t]!=-1) return 1;
return 0;
}
int main(){
n=read();m=read();k=read(); t=n+1;
for (int i=1;i<=t;i++) head[i]=-1;cnt=-1;
for (int i=1;i<=m;i++){
p[i].l=read();p[i].r=read();
p[i].f=read();p[i].c=read();
add(p[i].l,p[i].r,p[i].f,0);
}
while (bfs()){
for (int i=1;i<=n;i++) cur[i]=head[i];
do{
tot=dfs(1,big);
mflow+=tot;
}
while (tot);
}
printf("%d ",mflow);
for (int i=1;i<=t;i++) head[i]=-1;cnt=-1;
memset(ljb,0,sizeof(ljb));
add(n,t,mflow+k,0);
for (int i=1;i<=m;i++){
add(p[i].l,p[i].r,p[i].f,0);
add(p[i].l,p[i].r,big,p[i].c);
}
while (spfa()){
ans+=dis[t]*flow[t];
int now=t;
while (now!=1){
ljb[lst[now]].flow-=flow[t];
ljb[lst[now]^1].flow+=flow[t];
now=pre[now];
}
}
printf("%d",ans);
}
luogu2488 工作安排
费用流经典(套路)题 其实会了上面的修车 这道题就很简单了
先拆点，对于每位员工的每种愤怒值都拆成一个点，如果该愤怒值为x，维持该愤怒值的产品上限为y2，维持上一种愤怒值的产品上限为y2(题目保证愤怒值递增)，那么我们就把这个点和汇点连边，费用为x流量为(y2-y1)。
然后对于每种产品，我们和源点相连，费用为0流量为这种产品需要多少，之后产品和能生产自己的员工相连，流量为inf费用为0。
代码
#include<iostream>
#include<cstdio>
#include<queue>
#define big (1000000000 + 10)
#define maxn (10000 + 10)
using namespace std;
int dis[maxn],flow[maxn],pre[maxn],lst[maxn],p[maxn];
int head[1500000],h[1001][1001],a[1001][1001];
int n,m,cnt,s=0,t=5001;
long long ans;
bool vis[maxn];
int read(){
char c;int r=0,f=1;
c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
r=(r*10)+(c^48);
c=getchar();
}
return r*f;
}
struct edge{
int next,to,flow,dis;
}ljb[1500000];
void add_edge(int x,int y,int f,int c){
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].flow=f;
ljb[cnt].dis=c;
head[x]=cnt;
}
void add(int x,int y,int f,int c){
add_edge(x,y,f,c);
add_edge(y,x,0,-c);
}
queue<int> q;
bool spfa(){
for (int i=s;i<=t;i++) dis[i]=big,flow[i]=big,vis[i]=0,pre[i]=-1,lst[i]=0;
q.push(s);dis[s]=0;
while (!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]>dis[x]+ljb[i].dis && ljb[i].flow>0){
dis[y]=dis[x]+ljb[i].dis;
flow[y]=min(flow[x],ljb[i].flow);
pre[y]=x; lst[y]=i;
if (!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
if (pre[t]!=-1) return 1;
return 0;
}
int main(){
m=read();n=read();
for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
for (int i=1;i<=n;i++){
int x=read();
add(s,i,x,0);
}
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
a[j][i]=read();
for (int i=1;i<=m;i++){
p[i]=read();
for (int j=1;j<=p[i];j++) h[i][j]=read();
h[i][p[i]+1]=big;
for (int j=1;j<=p[i]+1;j++){
int x=read();
add(250+(i-1)*10+j,t,h[i][j]-h[i][j-1],x);
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j])
for (int k=1;k<=p[j]+1;k++)
add(i,250+(j-1)*10+k,big,0);
while (spfa()){
ans+=dis[t]*flow[t];
int now=t;
while (now!=s){
ljb[lst[now]].flow-=flow[t];
ljb[lst[now]^1].flow+=flow[t];
now=pre[now];
}
}
printf("%lld",ans);
}
luogu3425 KOS-DICING
由于题目给的不清楚所以这里解释一下：
有n个人，他们两两对决，共进行m轮游戏。现在给出每轮游戏是哪两个人对决，然后求出赢的最多的人至少可以赢多少场。注意，可以并列。
还是套路啊，这次我们会想到跳舞那道题。
跳舞那道题，就是二分能不能跳x首舞曲。同样的，我们这个题二分赢的最多的人能不能赢x场。这就好办了，我们从源点向每个人连一条边权为x的边，之后每两个参加同一轮游戏的人连到一个游戏上，边权为1，之后每个游戏都连到汇点，边权为1。这样只要你最后的流等于m，就说明你当前的x大于等于你要求的最终答案。
输出方案的话你只需要枚举一下所有的正向的连接玩家与游戏的边，如果边权为0就说明这场游戏是这条边的入点(from)这个人赢了，就标记上就好了。
需要注意两个细节：
1.每次跑图要记得把边都重构一下。
2.确定最终答案的过程要再二分里面进行，因为我们是二分到一个不能实现的答案才跳出来的。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define big (1000000000 + 10)
#define maxn (100000 + 10)
using namespace std;
int dis[maxn],head[maxn],cur[maxn],p[maxn],a[maxn],b[maxn];
int cnt,n,m,k,ans,tot,answer,s,t=20010;
inline char gc(){
static char BUFF[1000000],*S=BUFF,*T=BUFF;
return S==T&&(T=(S=BUFF)+fread(BUFF,1,1000000,stdin),S==T)?EOF:*S++;
}
inline int read(){
char c;int r=0,f=1;
c=gc();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=gc();
}
while (c>='0' && c<='9'){
r=(r*10)+(c^48);
c=gc();
}
return r*f;
}
struct edge{
int next,from,to,dis;
}ljb[maxn];
inline void add_edge(int x,int y,int z){
ljb[++cnt].next=head[x];
ljb[cnt].from=x;
ljb[cnt].to=y;
ljb[cnt].dis=z;
head[x]=cnt;
}
inline void add(int x,int y,int z){
add_edge(x,y,z);
add_edge(y,x,0);
}
queue<int> q;
inline bool bfs(){
for (int i=s;i<=t;i++) dis[i]=-1;
q.push(s); dis[s]=0;
while (!q.empty()){
int x=q.front(); q.pop();
for (int i=head[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==-1 && ljb[i].dis>0){
dis[y]=dis[x]+1;
q.push(y);
}
}
}
if (dis[t]!=-1) return 1;
return 0;
}
inline int dfs(int x,int low){
if (x==t) return low;
int sum=0;
for (int& i=cur[x];i!=-1;i=ljb[i].next){
int y=ljb[i].to;
if (dis[y]==dis[x]+1 && ljb[i].dis>0){
int flow=dfs(y,min(low,ljb[i].dis));
if (flow){
sum+=flow;
low-=flow;
ljb[i].dis-=flow;
ljb[i^1].dis+=flow;
if (!low) break;
}
}
}
if (!sum) dis[x]=-1;
return sum;
}
inline void pre(){
for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
for (int i=1;i<=n;i++) add(s,i,big);
for (int i=1;i<=m;i++){
add(a[i],i+10000,1);
add(b[i],i+10000,1);
add(i+10000,t,1);
}
}
inline bool dinic(int x) {
for (int i=0;i<=cnt;i+=2){
if (ljb[i].from==s) ljb[i].dis=x,ljb[i^1].dis=0;
if (ljb[i].to==t) ljb[i].dis=1,ljb[i^1].dis=0;
if (ljb[i].from<=10000 && ljb[i].to>10000)
ljb[i].dis=1,ljb[i^1].dis=0;
}
ans=0;
while (bfs()){
for (int i=s;i<=t;i++) cur[i]=head[i];
do{
tot=dfs(s,big);
ans+=tot;
}
while (tot);
}
if (ans==m) return 1;
return 0;
}
int main(){
n=read();m=read();
for (int i=1;i<=m;i++) a[i]=read(),b[i]=read();
pre();
int l=0,r=m;
while (l<=r){
int mid=(l+r)>>1;
if (dinic(mid)){
r=mid-1;
answer=mid;
for (int i=0;i<=cnt;i+=2)
if (ljb[i].from!=s && ljb[i].to!=t && ljb[i].dis==0)
p[ljb[i].to-10000]=ljb[i].from;
}
else l=mid+1;
}
printf("%d\n",answer);
for (int i=1;i<=m;i++)
if (a[i]==p[i]) puts("1");
else puts("0");
}
赞 赏
蒟蒻的邮箱:xmzl200201@126.com
