POJ 1966 Cable TV Network【SAP】

ret43543

　　
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[N][N];
int cmap[N][N];
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[MAXN],label[MAXN],neck[MAXN];         //当前弧，标号，瓶颈边的入点（姑且这么叫吧）   
int label_count[MAXN],back_up[MAXN],pre[MAXN];    //标号为i节点的数量，cur_flow的纪录,当前流路径中前驱  
//back_up表示当前流流到点i能达到的最大流量
int SAP(int map[][maxn],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[0]=v_count;
neck=s;//neck表示当前流的瓶颈点
max_flow = 0;
cur = s;
cur_flow = INF;
//循环代替递归
while(label<v_count)
{
back_up[cur]=cur_flow;
flag = false;//记录当前点是否存在下一层
//寻找当前可行流的下一点
for(i=cur_arc[cur];i<v_count;i++)
{
if(map[cur]!=0&&label==label[cur]-1)//寻找到下一层
{
flag=true;
cur_arc[cur]=i;//更新
//更新当前流
if(map[cur]<cur_flow)
{
cur_flow = map[cur];
neck=cur;
}else
neck=neck[cur];//瓶颈相对前驱节点不变
pre=cur;
cur = i;
if(i==t)//找到可行流
{
max_flow+=cur_flow;
while(cur!=s)
{
//当前弧的流量并非无限。。。。若无限，则无需减
if(map[pre[cur]][cur]!=INF)
{
map[pre[cur]][cur]-=cur_flow;
}
back_up[cur]-=cur_flow;
if(map[cur][pre[cur]]!=INF)
map[cur][pre[cur]]+=cur_flow;
cur=pre[cur];
}
cur = neck[t];//返回至瓶颈节点，继续做
cur_flow = back_up[cur];
}
break;
}
}
if(flag)continue;//下层已经找到
//未找到下层点
int nextid;
int min_label = v_count-1;
for(i=0;i<v_count;i++)
{
if(map[cur]!=0&&label<min_label)
{
min_label = label;
nextid = i;
}
}
label_count[label[cur]]--;
if(label_count[label[cur]]==0)break;//GAP优化
label[cur]=min_label+1;
cur_arc[cur]=nextid;
label_count[label[cur]]++;
if(cur!=s)//从栈中弹出一个节点
{
cur = pre[cur];
cur_flow = back_up[cur];
}
}
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[vv]=n+1;
map[uu][v]=n+1;
}
int i,j,t;
for(i=0;i<n;i++)
map[i+n]=1;
int ans = n;
int s = n;
for(i=0;i<n+n;i++)
for(j=0;j<n+n;j++)
cmap[j]=map[j];
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[t][j]=map[t][j];
}
}
printf("%d\n",ans);
}
return 0;
}