POJ 1149 PIGS【SAP】
POJ 1149 PIGS大意：
有m个猪圈和n个顾客，最初猪圈是锁着的。
每个顾客有其中的A把钥匙，需要买B头猪
顾客在买完猪便将门锁上，而且顾客是按照顺序来的。
商家可以对开着的猪圈里面的猪进行任意调配
分析：
构图
1.将猪圈编号为1,2，。。。。m;
2.将顾客编号为m+1,m+2,....m+n
3.源点为0,汇点为m+n+1
4.若猪圈i有a头牛，那么建立一条从0到i,流量为a的边
5.若顾客j是第一个能打开猪圈i的顾客，那么从猪圈i到顾客j之间建立边，流量无限大
6.若顾客j是能打开猪圈i的第k个顾客，第k-1个顾客为x,那么从顾客x到顾客j建立一条边
此题使用的最大流模板是SAP,BlueSky给的，很给力哦~
#include<stdio.h>
#include<string.h>
const int MAXN = 1000+100+2;
const int maxn = MAXN;
int map;
const int INF = 100000+5;
int son;
int cur_arc,label,neck; //当前弧，标号，瓶颈边的入点（姑且这么叫吧）
int label_count,back_up,pre; //标号为i节点的数量，cur_flow的纪录,当前流路径中前驱
//back_up表示当前流流到点i能达到的最大流量
int SAP(int map[],int v_count,int s,int t) //邻接矩阵，节点总数，始点，汇点
{
int i;
int cur_flow,max_flow,cur; //当前流，最大流，当前节点，最小标号，临时变量
char flag; //标志当前是否有可行流
memset(label,0,sizeof(label));
memset(label_count,0,sizeof(label_count));
memset(cur_arc,0,sizeof(cur_arc));//cur_arc为与i相连最近的点
label_count=v_count;
neck=s;//neck表示当前流的瓶颈点
max_flow = 0;
cur = s;
cur_flow = INF;
//循环代替递归
while(label<v_count)
{
back_up=cur_flow;
flag = false;//记录当前点是否存在下一层
//寻找当前可行流的下一点
for(i=cur_arc;i<v_count;i++)
{
if(map!=0&&label==label-1)//寻找到下一层
{
flag=true;
cur_arc=i;//更新
//更新当前流
if(map<cur_flow)
{
cur_flow = map;
neck=cur;
}else
neck=neck;//瓶颈相对前驱节点不变
pre=cur;
cur = i;
if(i==t)//找到可行流
{
max_flow+=cur_flow;
while(cur!=s)
{
//当前弧的流量并非无限。。。。若无限，则无需减
if(map]!=INF)
{
map]-=cur_flow;
}
back_up-=cur_flow;
if(map]!=INF)
map]+=cur_flow;
cur=pre;
}
cur = neck;//返回至瓶颈节点，继续做
cur_flow = back_up;
}
break;
}
}
if(flag)continue;//下层已经找到
//未找到下层点
int nextid;
int min_label = v_count-1;
for(i=0;i<v_count;i++)
{
if(map!=0&&label<min_label)
{
min_label = label;
nextid = i;
}
}
label_count]--;
if(label_count]==0)break;//GAP优化
label=min_label+1;
cur_arc=nextid;
label_count]++;
if(cur!=s)//从栈中弹出一个节点
{
cur = pre;
cur_flow = back_up;
}
}
return max_flow;
}
int main()
{
int n,m;
while(scanf("%d%d",&m,&n)!=EOF)
{
int i;
int s = 0;
int t = m+n+1;
memset(map,0,sizeof(map));
for(i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
son=i;
map+=x;//建立从源点到猪的边，权重为猪圈的猪的个数
}
for(i=1;i<=n;i++)
{
int A,B,x;
scanf("%d",&A);
while(A--)
{
scanf("%d",&x);
map]=INF;
son=i+m;
}
scanf("%d",&B);
map=B;
}
printf("%d\n",SAP(map,n+m+2,s,t));
}
return 0;
}
页:
[1]