POJ 1966 Cable TV Network【SAP】
http://poj.org/problem?id=1966
POJ 1966 Cable TV Network
算法核心：网络流-SAP
#include<stdio.h>
#include<string.h>
const int N = 50*2+5;
const int INF = N;
const int MAXN=N;
const int maxn = N;
int map;
int cmap;
int getNum()
{
char c;
int num = 0;
while(c=getchar())
{
if(c<='9'&&c>='0')break;
}
while(c<='9'&&c>='0')
{
num=num*10+c-'0';
c = getchar();
}
return num;
}
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",&n,&m)!=EOF)
{
memset(map,0,sizeof(map));
int mid = n;
while(m--)
{
int u =getNum();
int v = getNum();
int uu=u+n;
int vv=v+n;
map=n+1;
map=n+1;
}
int i,j,t;
for(i=0;i<n;i++)
map=1;
int ans = n;
int s = n;
for(i=0;i<n+n;i++)
for(j=0;j<n+n;j++)
cmap=map;
for(i=1;i<n;i++)
{
//if(map==0)
{
int temp = SAP(cmap,n+n,s,i);
if(ans>temp)ans = temp;
for(t=0;t<n+n;t++)
for(j=0;j<n+n;j++)
cmap=map;
}
}
printf("%d\n",ans);
}
return 0;
}
页:
[1]