有源汇上下界最小流 BZOJ 2502: 清理雪道

2502: 清理雪道

Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1039  Solved: 561 [Submit][Status][Discuss]

Description

       滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。 由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

Input

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为m_i (0 <= m_i < n) ，后面共有m_i个整数，由空格隔开，每个整数a_ij互不相同，代表从地点i下降到地点a_ij的斜坡。每个地点至少有一个斜坡与之相连。

Output

       输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

Sample Input

8 1 3 1 7 2 4 5 1 8 1 8 0 2 6 5 0

Sample Output

4

题意就是给你一个拓扑图，每条边流量下限为1

有一个原点可以向每个点流流量，问最小流多少

这里我们就来解决这个有源汇上下界最小流问题

先跑出可行流

但可行流不一定最小(可以随手YY)

那么我们如何搞掉多余的流量呢

考虑由S->T的过程是增广

由T->S的过程就是对S->T的流的缩减（感性/理性理解）

所以在得到可行流后

做T->S的最大流 并将其从答案减去就好了

注意：

在我们求解可行流的过程中，应用新源汇对所有点连边

此题中特殊在于源汇没有流量限制，所以连不连无所谓

第二遍跑dinic是在残量网络上跑

不能跑完之后用边权和求最大流

#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(int x) {if(x<0)x=-x,putchar('-');if(x>=10)print(x/10);putchar(x+'0');} const int N=210,M=100100,inf=0X3f3f3f3f; int ecnt=1,last[N]; struct EDGE{int to,nt,val;}e[M]; inline void readd(int u,int v,int val) {e[++ecnt]=(EDGE){v,last[u],val};last[u]=ecnt;} inline void add(int u,int v,int val) {readd(u,v,val);readd(v,u,0);} int in[N]; int n,ans; int S=N-2,T=N-1; int d[N],q[N]; bool bfs(int s,int t) { memset(d,0,sizeof(d)); register int i,head=0,tail=1,u; q[head]=s;d[s]=1; while(head<tail) { u=q[head++]; for(i=last[u];i;i=e[i].nt)if(!d[e[i].to]&&e[i].val) { d[e[i].to]=d[u]+1; q[tail++]=e[i].to; } } return d[t]; } int dfs(int u,int lim,int aim) { if(u==aim||!lim)return lim; int res=0,tmp; for(int i=last[u];i;i=e[i].nt)if(e[i].val&&d[e[i].to]==d[u]+1) { tmp=dfs(e[i].to,min(e[i].val,lim),aim); res+=tmp;lim-=tmp;e[i].val-=tmp;e[i^1].val+=tmp; if(!tmp)d[e[i].to]=-1;if(!lim)break; } return res; } int dinic(int s,int t) {int res=0;while(bfs(s,t))res+=dfs(s,inf,t);return res;} int main() { n=read(); register int i,j,num,v,sum; for(i=1;i<=n;++i) { num=read(); for(j=1;j<=num;++j) {v=read();in[i]--;in[v]++;add(i,v,inf);} } for(i=1;i<=n;++i)add(S,i,inf),add(i,T,inf); int SS=N-4,TT=N-3; for(int i=1;i<=n;++i)in[i]>0?add(SS,i,in[i]):add(i,TT,-in[i]); add(T,S,inf); dinic(SS,TT); sum=e[ecnt].val; e[ecnt].val=e[ecnt^1].val=0; for(i=last[SS];i;i=e[i].nt)e[i].val=e[i^1].val=0; for(i=last[TT];i;i=e[i].nt)e[i].val=e[i^1].val=0; print(sum-dinic(T,S));puts(""); return 0; } /* 8 1 3 1 7 2 4 5 1 8 1 8 0 2 6 5 0 4 */