网络流裸体
第一问最大流跑一跑
第二问新建一个点连边到1 容量k费用0 再对所有的边复制一条边出来 容量为inf 费用为w
然后跑最小费用最大流
这题最大流用ek可过
#include <cstdio> #include <algorithm> #include <cstring> #define clr(x) memset(x,0,sizeof(x)) using namespace std; void read(int &x){ char c; while((c=getchar())<'0' || c>'9');x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0'; } const int N=100010,inf=308888888; struct Ask{ int u,v,c,w; void read2(){read(u),read(v);read(c);read(w);} }ask[N]; int n,m,c[N],to[N],nxt[N],now[N],cap[N],tail=1,q[N],from[N],dis[N],inq[N],k,ans; void add(int u,int v,int ci,int capi){ to[++tail]=v;nxt[tail]=now[u];now[u]=tail;c[tail]=ci;cap[tail]=capi; to[++tail]=u;nxt[tail]=now[v];now[v]=tail;c[tail]=-ci;cap[tail]=0; } bool spfa(int s,int t){ int l=0,r=0; clr(from);clr(inq); for(int i=1;i<=n+2;i++) dis[i]=inf; q[++r]=s;dis[s]=0;inq[s]=1; while(l<r){ int u=q[(++l)%N];inq[u]=0; for(int i=now[u];i;i=nxt[i]) if(cap[i]>0 && dis[to[i]]>dis[u]+c[i]){ int v=to[i]; dis[v]=dis[u]+c[i]; from[v]=i; if(!inq[v]) q[(++r)%N]=v; } } return dis[t]!=inf; } int augument(int s,int t,int type){ int fl=inf,ret=0; for(int tmp=t;tmp!=s;){ int e=from[tmp]; fl=min(cap[e],fl); tmp=to[e^1]; } for(int tmp=t;tmp!=s;){ int e=from[tmp]; cap[e]-=fl;cap[e^1]+=fl; ret+=fl*c[e]; tmp=to[e^1]; } return type?ret:fl; } int main(){ //freopen("1834.in","r",stdin);freopen("1834.out","w",stdout); read(n);read(m);read(k); for(int i=1;i<=m;i++) { ask[i].read2(); add(ask[i].u,ask[i].v,0,ask[i].c); } while(spfa(1,n)) ans+=augument(1,n,0); printf("%d ",ans);ans=0; for(int i=1;i<=m;i++) add(ask[i].u,ask[i].v,ask[i].w,inf); add(n+1,1,0,k); while(spfa(n+1,n)) ans+=augument(n+1,n,1); printf("%d",ans); }
这种限制节点经过次数的估计就是网络流了
新建源汇s t
把一个点拆成两个,中间连接一条容量为经过次数的边
对于每一个蜥蜴,从s向这个点的入点连边,容量为1,表示有一条蜥蜴。对于每一个点可达的点从出点连边,容量正无穷,能跳出的向t连边,容量正无穷。跑最大流即可
dinic的时候不要忘记重置cur数组,一直死循环…………
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; //点ij为2*(c*(i-1)+j)入和2*(c*(i-1)+j)+1出 s=r*c*2+2 t=r*c*2+3 const int N=200010,INF=209999999; int to[N],from[N],fl[N],tail=1,pre[N],now[N],ans,d[N],vis[N],q[N*2],L,R,cur[N],r,c,di,tmp,g[50][50],xiyi; inline int o(int i,int j){return 2*(c*(i-1)+j);} void add(int u,int v,int f){ to[++tail]=v;pre[tail]=now[u];now[u]=tail;fl[tail]=f; to[++tail]=u;pre[tail]=now[v];now[v]=tail;fl[tail]=0; } bool bfs(int s,int t){ memset(vis,0,sizeof(vis)); L=R=0;q[++R]=s;vis[s]=1;d[s]=0; for(int x=q[++L];L<=R;x=q[++L]) for(int i=now[x];i;i=pre[i]) if(fl[i]>0 && !vis[to[i]]) d[to[i]]=d[x]+1,vis[to[i]]=1,q[++R]=to[i]; return vis[t]; } int dfs(int x,int t,int a){ if(x==t || a==0) return a; int flow=0,f; for(int &i=cur[x];i;i=pre[i]) if(d[to[i]]==d[x]+1 && (f=dfs(to[i],t,min(a,fl[i])))>0){ fl[i]-=f;fl[i^1]+=f;flow+=f;a-=f; if(a==0) break; } return flow; } int main(){ //freopen("1066.in","r",stdin);freopen("1066.out","w",stdout); scanf("%d%d%d\n",&r,&c,&di); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++) { g[i][j]=getchar()-'0'; if(g[i][j]) add(o(i,j),o(i,j)^1,g[i][j]); } getchar(); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(g[i][j]) for(int x=-di;x<=di;x++) for(int y=-di;y<=di;y++) if(abs(x)+abs(y)<=di && i+x>0 && i+x<=r && j+y>0 && j+y<=c && g[i+x][j+y] && ((i+x)!=i || (j+y)!=j)) add(o(i,j)^1,o(i+x,j+y),INF); for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ tmp=getchar(); if(tmp=='L') xiyi++,add(2*r*c+2,o(i,j),1); } getchar(); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(g[i][j] && min(min(r+1-i,i),min(c+1-j,j)) <= di) add(o(i,j)+1,2*r*c+3,INF); while(bfs(2*r*c+2,2*r*c+3)) { for(int i=1;i<=2*r*c+3;i++) cur[i]=now[i]; ans+=dfs(2*r*c+2,2*r*c+3,INF); } ans=xiyi-ans; printf("%d",ans); return 0; }
今天看到这题,这TM不是上星期BC的最后一题吗!!!!!!!!于是整个人都不好了,为什么我没有早点开始做BZOJ!!
于是用上星期在题解里看到的方法A了这题
这道题的思路是拆点
由于每一个人的选择 只会对后边来修车的人有影响 我们只要考虑这个人是倒数第几个人来修车的就好了
新建s,t。
将每个店员拆成n个点,其中第t个点代表倒数第t个修。比如 我是第一个人 是倒数第二个人来修车的,那么我这个选择就会让我自己和我后面的人总共等2*T[i][j]的时间,所以只要连一条容量为1的边,费用为倒数第k个 k*T[i][j]就好了。剩下来就是 s连到每个人容量1费用0,店员连到t,容量1,费用0就好了
巧妙的构图 考试的时候根本没想到。
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N=100010,INF=1049999654; LL n,m,to[N*4],from[N*4],pre[N*4],now[N*2],cost[N*4],flow[N*4],tail=1,prev[N],dis[N],ans,inq[N],l,r,q[N],tmp; void add(int u,int v,int f,int co){ to[++tail]=v;from[tail]=u;flow[tail]=f;pre[tail]=now[u];now[u]=tail;cost[tail]=co; to[++tail]=u;from[tail]=v;flow[tail]=0;pre[tail]=now[v];now[v]=tail;cost[tail]=-co; } bool spfa(int s,int t){ for(int i=1;i<=n+m*n+2;i++) inq[i]=0,dis[i]=INF,prev[i]=0; l=r=0;dis[s]=0;q[++r]=s;inq[s]=1; while(l<r){ int x=q[(++l)%N];inq[x]=0; for(int i=now[x];i;i=pre[i]) if(flow[i]>0 && dis[to[i]]>dis[x]+cost[i]){ dis[to[i]]=dis[x]+cost[i];prev[to[i]]=i; if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1; } } return dis[t]!=INF; } void zg(int s,int t){ LL f=INF; for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]); for(int i=t;i!=s;i=from[prev[i]]) {flow[prev[i]]-=f;flow[prev[i]^1]+=f;ans+=f*cost[prev[i]];} } int main(){ scanf("%lld%lld",&m,&n); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) { scanf("%lld",&tmp); for(int T=1;T<=n;T++) add(i,j*n+T,1,T*tmp); } } for(int i=n+1;i<=n+m*n;i++) add(i,n+m*n+2,1,0); for(int i=1;i<=n;i++) add(n+m*n+1,i,1,0); while(spfa(n+m*n+1,n+m*n+2)) zg(n+m*n+1,n+m*n+2); printf("%.2lf",(double)ans/n); }
听说这道题可以用线性规划的方法水过去,但是这是一道网络流题
以下引用自百度
设每个时间i都需要有至少Ai个志愿者,设每种志愿者i使用了xi个,那么我们对于每个时间点都可以列出一个不等式:x1+x2+x3+...+xn>=Ai(其中如果第i类志愿者不能在该区间工作则xi固定为0)。
最后要求最小化w1*x1+w2*x2+x3*x3+...+wn*xn(其中wi是第i种志愿者的单位价格)。
这正是一个线性规划的问题。
那么我们是否可以转化为网络流来求解呢?
当然是可以哒~
现在我们将每个点的Ai取反,变成-Ai,这样他就成了一个“坑”了(相对于y=0而言),我们从源点S给最左边的时间点引流,流的大小为U(U为大整数),然后每个时间点i向时间点i+1建边(i,i+1,U-Ai,0),最后设汇点为最右端的时间点。
现在,如果所有时间点的Ai都为0,那么显然,汇点的流量恰好等于U。
问题来了,现在我们有的Ai不等于0了,那么显然源点到汇点的流量被这些“坑”所截断了,怎么解决这一个问题?
假设志愿者工作的时间为【Li,Ri】,且该种志愿者单位花费为Ci,则我们建边(Li,Ri+1,INF,Ci),表示我们雇佣了一些志愿者“填坑”来了,如果雇佣了xi个志愿者,则说明将该区间内的所有“坑”的深度填掉了xi(当然可能有的坑在“填坑”行动后高于y=0,那也无所谓了嘛,多多益善~)。
那么现在是不是看起来思路有一点清晰了?
于是志愿者的作用就是一个人可以填一个区间的“坑”(好厉害!),然后需要每种志愿者选择一些使得花费最小的情况下填掉所有的“坑”,就是这样~
最后就是让费用流帮我们选择志愿者的时候了~
于是我们按照上面的方法跑完一遍最小费用最大流,如果流量等于U,则说明满流(志愿者们成功填掉了所有的坑,同志们辛苦了~),此时的记录的cost就是最小值(cost为算法记录的最小费用)。如果流量不等于U则无解。
这时我们又收获了一种费用流的模型:初始给一道大流,然后将有至少覆盖次数限制的点(边)的权值取反变成“坑”,最后区间覆盖就等于“填坑”,只要最后的流量等于大流的流量,就有解。
或者看这个题解 http://blog.csdn.net/fzhvampire/article/details/50889187
接下来是代码
#include <cstdio> #include <algorithm> using namespace std; const int N=100010,INF=1000000000; int to[N*2],from[N*2],pre[N*2],cost[N*2],flow[N],q[N],l,r,inq[N],dis[N],now[N],prev[N],tail=1,n,m,a,s,t,c,left=INF,ans; void add(int u,int v,int cap,int co){to[++tail]=v;from[tail]=u;pre[tail]=now[u];now[u]=tail;cost[tail]=co;flow[tail]=cap;} bool spfa(int s,int t){ for(int i=1;i<=n+2;i++) dis[i]=INF; l=r=0;q[++r]=s;inq[s]=1;dis[s]=0; while(l<r){ int x=q[(++l)%N];inq[x]=0; for(int i=now[x];i;i=pre[i]) if(flow[i]>0){ if(dis[to[i]] > dis[x] + cost[i]) { dis[to[i]]=dis[x]+cost[i],prev[to[i]]=i; if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1; } } } return dis[t]!=INF; } int zg(int s,int t){ int f=INF,sum=0; for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]); for(int i=t;i!=s;i=from[prev[i]]) flow[prev[i]]-=f,flow[prev[i]^1]+=f,sum+=cost[prev[i]]*f; return sum; } int main(){ //freopen("1061.in","r",stdin);freopen("1061.out","w",stdout); scanf("%d%d",&n,&m); add(n+2,1,INF,0);add(1,n+2,0,0); for(int i=1;i<=n;i++) scanf("%d",&a),add(i,i+1,INF-a,0),add(i+1,i,0,0); for(int i=1;i<=m;i++) scanf("%d%d%d",&s,&t,&c),add(s,t+1,INF*2,c),add(t+1,s,0,-c); while(spfa(n+2,n+1)) ans+=zg(n+2,n+1); printf("%d",ans); return 0; }
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=200000; int e[N*2],pre[N*2],c[N*2],flow[N*2],now[N],d[N],vis[N],tail=1,cur[N],n,m,q[N],v,ans,a,b; void add(int u,int v,int cap){e[++tail]=v;c[tail]=cap;pre[tail]=now[u];now[u]=cur[u]=tail;} bool bfs(int s,int t){ int l=0,r=0; memset(vis,0,sizeof(vis)); q[++r]=s;d[s]=0;vis[s]=1; while(l<r){ int x=q[++l]; for(int i=now[x];i;i=pre[i]) if(!vis[e[i]] && c[i]>0) { q[++r]=e[i];vis[e[i]]=1;d[e[i]]=d[x]+1; } } return vis[t]; } int dfs(int x,int a){ if(x==n+m+2 || a==0) return a; int flow=0,f; for(int &i=cur[x];i;i=pre[i]) if(d[x]+1==d[e[i]] && (f=dfs(e[i],min(a,c[i])))>0){ c[i]-=f;c[i^1]+=f;flow+=f;a-=f; if(a==0) break; } return flow; } void print(int a){ printf("Edges of %d :",a); for(int i=now[a];i;i=pre[i]) if(c[i]) printf("%d(%d) ",e[i],c[i]);printf("\n"); } int main(){ freopen("1497.in","r",stdin);freopen("1497.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&v),add(i,n+m+2,v),add(n+m+2,i,0); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&v); add(n+m+1,i+n,v); add(i+n,n+m+1,0); add(i+n,a,2099999999+1);add(a,i+n,0); add(i+n,b,2099999999+1);add(b,i+n,0); ans+=v; } //print(11);for(int i=6;i<=10;i++) print(i);for(int i=1;i<=5;i++) print(i);print(12); while(bfs(n+m+1,n+m+2)) { for(int i=1;i<=n+m+2;i++) cur[i]=now[i]; ans-=dfs(n+m+1,2099999999); } printf("%d",ans); return 0; }