网络流专题
很明显的一道最大流匹配题目
唯一要注意的点是题目要求是一头牛只能搭配一个饮料和事物
所以要拆点
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define INF 0x7fffffff
const int maxn=505;
const int maxm=200000;
int N,F,D,cnt,S,T;
int head[maxm],num[maxn],maxflow;
struct node{
int to,next,w;
}edg[maxm];
void add(int u,int v,int w){
++cnt;
edg[cnt].to=v;
edg[cnt].w=w;
edg[cnt].next=head[u];
head[u]=cnt;
}
queueQ;
bool bfs(){
while(!Q.empty()){
Q.pop();
}
for(int i=S;i<=T+N;i++)num[i]=-1;
num[S]=1;
Q.push(S);
while(!Q.empty()){
int now=Q.front();Q.pop();
for(int i=head[now];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&num[to]==-1){
num[to]=num[now]+1;
Q.push(to);
}
}
}
return (num[T]!=-1);
}
int dfs(int u,int f){
if(u==T){
return f;
}
int flow;
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&num[to]==num[u]+1&&(flow=dfs(to,min(f,w)))){
edg[i].w-=flow;
edg[i^1].w+=flow;
return flow;
}
}
return 0;
}
void dinic(){
int minn;
while(bfs()){
while(minn=dfs(S,INF)){
maxflow+=minn;
}
}
}
int main(){
scanf("%d%d%d",&N,&F,&D);
cnt++;
S=1,T=1+N+F+D+1;
for(int i=1;i<=F;i++)add(S,i+1,1),add(i+1,S,0);
for(int i=1;i<=D;i++)add(i+1+F+N,T,1),add(T,i+1+F+N,0);
for(int i=1;i<=N;i++)add(1+F+i,1+F+N+D+1+i,1),add(1+F+N+D+i+1,1+F+i,0);
for(int i=1;i<=N;i++){
int ff,dd;
scanf("%d%d",&ff,&dd);
for(int t,j=1;j<=ff;j++){
scanf("%d",&t);
add(t+1,1+F+i,1);
add(1+F+i,t+1,0);
}
for(int t,j=1;j<=dd;j++){
scanf("%d",&t);
add(1+F+N+D+1+i,1+F+N+t,1);
add(1+F+N+t,1+F+N+D+1+i,0);
}
}
dinic();
printf("%d\n",maxflow);
return 0;
}
其实网络流的题目还是很明显的
你读完题目就知道这个是网络流的题目
建边
超源点S连接每个试题，因为每个试题只能选一次，所以边权为1
每个试题连接多个不同的类型，因为每个试题只能代表一种类型，所以边权为1
每个类型连接超汇点T，因为每个类型有不同的要求数量，所以边权具体题目给出
输出
这个题关键就是输出
记得dinic算法是建立了反向边的，所以只要该类型通向试题的反向边权大于0，就可以输出
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define INF 0x7fffffff
const int maxn=2e3+5;
const int maxm=1e6+5;
int K,N,M,S,T,ans,cnt;
int head[maxm],num[maxn],vis[maxn];
queueQ;
struct node{
int to,w,next;
}edg[maxm];
void add(int u,int v,int w){
++cnt;
edg[cnt].to=v;
edg[cnt].w=w;
edg[cnt].next=head[u];
head[u]=cnt;
}
bool bfs(){
while(!Q.empty()){
Q.pop();
}
for(int i=S;i<=T;i++)vis[i]=-1;
vis[S]=1;
Q.push(S);
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&vis[to]==-1){
vis[to]=vis[u]+1;
Q.push(to);
}
}
}
return (vis[T]!=-1);
}
int dfs(int u,int f){
if(u==T)return f;
int flow=0;
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&vis[to]==vis[u]+1&&(flow=dfs(to,min(w,f)))){
edg[i].w-=flow;
edg[i^1].w+=flow;
return flow;
}
}
return 0;
}
void dinic(){
while(bfs()){
int ff;
while(ff=dfs(S,INF)){
ans+=ff;
}
}
}
void print(int u){
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w>0&&to<=S+N)
printf(" %d",to-S);
}
}
int main(){
scanf("%d%d",&K,&N);
++cnt;S=1;T=1+N+K+1;
for(int i=1;i<=K;i++){
scanf("%d",&num[i]),M+=num[i];
add(S+N+i,T,num[i]);
add(T,S+N+i,0);
}
for(int i=1;i<=N;i++)add(S,S+i,1),add(S+i,S,0);
for(int i=1;i<=N;i++){
int p;scanf("%d",&p);
while(p--){
int t;scanf("%d",&t);
add(S+i,S+N+t,1);
add(S+N+t,S+i,0);
}
}
dinic();
if(ans 
分析
很好能get到这个题是最小割的题目
关键的点就是在于朋友之间建边要双向建边，一开始我一直没想明白，做题的时候也很难想到
那就说明对最小割的理解还不够深刻
一般我们建立S->T的单向边是因为只有S流向T，而这个题不一样
尽管A和B两人的意见不一样，那可以B妥协A，A可以妥协B，就是说
S可以流向T，T同样可以流向S
点击查看代码
#include
#define il inline
using namespace std;
const int N=100005,inf=23333333;
int n,m,s,t=520,h[N],cnt=1,dis[N],ans;
struct edge{
int to,net,v;
}e[N*4];
il void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;
e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt;
}
queueq;
il bool bfs()
{
memset(dis,-1,sizeof(dis));
q.push(s),dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].net)
if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,q.push(e[i].to);
}
return dis[t]!=-1;
}
il int dfs(int u,int op)
{
if(u==t)return op;
int used=0;
for(int i=h[u];i;i=e[i].net)
{
int v=e[i].to;
if(dis[v]==dis[u]+1&&e[i].v>0)
{
used=dfs(v,min(op,e[i].v));
if(!used)continue;
e[i].v-=used,e[i^1].v+=used;
return used;
}
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=n;i++){
scanf("%d",&x);
if(x==1)add(s,i,1);
else add(i,t,1);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y,1),add(y,x,1);
}
while(bfs())ans+=dfs(s,inf);
cout< 
这是最小割的经典题目类型
最大权闭合图
建图：
S与每个实验相连，边权为资金费
T与每个仪器相连，边权为消耗费用（相当于已经取绝对值了）
每个实验与相应的仪器相连，边权设为无穷大（因为割边一定不能割实验与仪器的边）
最后就是跑一遍dinic最大流
最大流＝最小割
最大权闭合子图的权值和 = max{被选择的点权和} = 正点权和?min{没被选择的正权点之和 + 被选择的负权点绝对值和} = 正点权和?最小割
最后一个要解决的问题就是要输出这个最大权闭合图
考虑最后一次bfs，能够到达的点就是在该图内
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define inf 0x7fffffff
#define ll long long
const int maxn=155;
const int maxm=1e6;
int S,T,M,N,cnt,tot,ans;
int head[maxn],dp[maxn];
struct node{
int to,w,next;
}edg[maxm];
void add(int u,int v,int w){
edg[++cnt].next=head[u];edg[cnt].to=v;edg[cnt].w=w;head[u]=cnt;
edg[++cnt].next=head[v];edg[cnt].to=u;edg[cnt].w=0;head[v]=cnt;
}
queueQ;
bool bfs(){
while(!Q.empty()){
Q.pop();
}
for(int i=S;i<=T;i++)dp[i]=-1;
dp[S]=1;
Q.push(S);
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&dp[to]==-1){
dp[to]=dp[u]+1;
Q.push(to);
}
}
}
return dp[T]!=-1;
}
int dfs(int u,int f){
if(u==T)return f;
int flow=0;
for(int i=head[u];i;i=edg[i].next){
int to=edg[i].to,w=edg[i].w;
if(w&&dp[to]==dp[u]+1&&(flow=dfs(to,min(f,w)))){
edg[i].w-=flow;
edg[i^1].w+=flow;
return flow;
}
}
return 0;
}
void dinic(){
while(bfs()){
int minn;
while(minn=dfs(S,inf)){
ans+=minn;
}
}
}
int main(){
++cnt;
S=0;T=150;
scanf("%d%d",&M,&N);
for (int i = 1,c; i <= M; i++) {
scanf("%d", &c), tot += c;
add(S, i, c);
while (getchar() == ' ') {
scanf("%d", &c);
add(i, c + M, inf);
}
}
for(int i=1,c;i<=N;i++){
scanf("%d",&c);
add(i+M,T,c);
}
dinic();
for (int i = 1; i <= M; i++) if (dp[i]!=-1) cout << i << ' '; puts("");
for (int i = 1; i <= N; i++) if (dp[i + M]!=-1) cout << i << ' '; puts("");
printf("%d\n",tot-ans);
return 0;
}
又是一道最大流模板
因为每个人只能选一个房间，所以对每个人进行拆点，最后套个dinic模板即可
点击查看代码
#include
using namespace std;
#define open(s) freopen( s".in", "r", stdin ), freopen( s".out", "w", stdout )
#define MAXN 405
#define MAXM 40005
int n, p, q;
int hd[MAXN], nxt[MAXM << 1], to[MAXM << 1], val[MAXM << 1], tot(1);
int ans, dis[MAXN];
queue Q;
int x, y;
int S, T;
void Add( int x, int y, int z ){ nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; val[tot] = z; }
bool BFS(){
while( !Q.empty() ) Q.pop();
memset( dis, 0, sizeof dis );
Q.push(S); dis[S] = 1;
while( !Q.empty() ){
x = Q.front(); Q.pop();
for ( int i = hd[x]; i; i = nxt[i] )
if ( val[i] && !dis[to[i]] ){
dis[to[i]] = dis[x] + 1;
Q.push( to[i] );
if ( to[i] == T ) return 1;
}
}
return 0;
}
int DFS( int x, int fl ){
if ( x == T ) return fl;
int k;
for ( int i = hd[x]; i ; i = nxt[i] ){
if ( val[i] && dis[to[i]] == dis[x] + 1 ){
k = DFS( to[i], min( fl, val[i] ) );
if(!k)continue;
val[i] -= k; val[i^1] += k;
return k;
}
}
return 0;
}
int main(){
scanf( "%d%d%d", &n, &p, &q );
S = 0; T = 1 + n + n + p + q;
for ( int i = 1; i <= n; ++i ) Add( i, i + n, 1 ), Add( i + n, i, 0 );
for ( int i = 1; i <= p; ++i ) Add( S, i + n + n, 1 ), Add( i + n + n, S, 0 );
for ( int i = 1; i <= q; ++i ) Add( i + n + n + p, T, 1 ), Add( T, i + n + n + p, 0 );
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= p; ++j ){
int t; scanf( "%d", &t );
if ( t ) Add( j + n + n, i, 1 ), Add( i, j + n + n, 0 );
}
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= q; ++j ){
int t; scanf( "%d", &t );
if ( t ) Add( i + n, j + n + n + p, 1 ), Add( j + n + n + p, i + n, 0 );
}
int t;
while( BFS() )
while( ( t = DFS( S, 0x7f7f7f7f ) ) > 0 ) ans += t;
printf( "%d\n", ans );
return 0;
}
这个题目特别点在于要求删点
那么就拆点：
x拆为（x,x'）容量为1
原图边x->y 为无向边，所以变为x'->y和y'->x容量均为无穷大
割点x相当于割掉x->x'这条边
因为要经过x连通的边没有了x->x'这条边都联通不了
因为至少满足两个点不连通整个图就不联通了
最后枚举源点和汇点即可
点击查看代码
const int N = 100, M = 5e4+7, INF = 0x3f3f3f3f;
int s1,t1,n,m;
int head[N<<1],ver[M],nex[M],edge[M],tot;
int a[N * N],b[N * N],deep[N<<1];
inline void add(int x,int y,int z){//正边反边
ver[++tot] = y;edge[tot] = z;
nex[tot] = head[x];head[x] = tot;
ver[++tot] = x;edge[tot] = 0;
nex[tot] = head[y];head[y] = tot;
}
inline bool bfs(){
memset(deep,0,sizeof deep);
queueq;
q.push(s1);
deep[s1] = 1;//分层
while(q.size()){
int x = q.front();
q.pop();
for(int i = head[x];i;i = nex[i]){
int y = ver[i],z = edge[i];//剩余容量>0才属于残量网络
if(z > 0 && !deep[y]){//不只是更新deep数组，是在残量网络上更新deep数组
q.push(y);
deep[y] = deep[x] + 1;
if(y == t1)return true;
}
}
}
return false;
}
inline int dinic(int x,int flow){
if(x == t1)return flow;
int res = flow;
for(int i = head[x];i && res;i = nex[i]){
int y = ver[i],z = edge[i];
if(z > 0 && (deep[y] == deep[x] + 1)){
int k = dinic(y,min(res,z));
if(!k)deep[y] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
res -= k;
}
}
return flow - res;
}
int main(){
while(cin>>n>>m){
for(int i = 0;i < m;++i){
char str[20];
scanf("%s",str);
a[i] = b[i] = 0;
int j;
for(j = 1;str[j] != ',';j++)
a[i] = a[i] * 10 + (str[j] - '0');
for(j++;str[j] != ')';j++)
b[i] = b[i] * 10 + (str[j] - '0');
}
int ans = INF;
for (s1 = 0; s1 < n; s1++)
for (t1 = 0; t1 < n; t1++)
if(s1 != t1){
memset(head,0,sizeof head);
tot = 1;
int maxflow = 0;
for(int i = 0;i < n;++i){
if(i == s1 || i == t1)//i是入点,i+n是出点
add(i,i + n,INF);//防止被割断
else add(i,i + n,1);
}
for(int i = 0;i < m;++i){
add(a[i] + n,b[i],INF);//不能割
add(b[i] + n,a[i],INF);
}
while(bfs()){
int num;
while((num = dinic(s1,INF)))
maxflow += num;
}
ans = min(ans,maxflow);
}
if(n <= 1 || ans == INF)ans = n;
cout<