上学路线(递归sap-不完全)

Problem 2 上学路线(route.cpp/c/pas)

【题目描述】

可可和卡卡家住马赛克市的东郊,每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。

马赛克市一共设有N个公交车站,不妨将它们编号为1…N的自然数,并认为可可和卡卡家住在1号汽车站附近,而他们学校在N号汽车站。市内有M条直达汽车路线,执行第i条路线的公交车往返于站点pi和qi之间,从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N)

两个人坐在电脑前,根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子,他想趁卡卡不备,在卡卡的输入数据中删去一些路线,从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci:删去路线的ci越大卡卡就越容易发现这个玩笑,可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。

马赛克市的公交网络十分发达,你可以认为任意两个车站间都可以通过直达或转车互相到达,当然如果在你提供的删除方案中,家和学校无法互相到达,那么则认为上学需要的最短为正无穷大:这显然是一个合法的方案。

 

【输入格式】

输入文件中第一行有两个正整数N和M,分别表示马赛克市公交车站和公交汽车路线的个数。以下M行,每行(第i行,总第(i+1)行)用四个正整数(之间由一个空格隔开)描述第i条路线:pi, qi, ti, ci;具体含义见上文描述。

【输出格式】

输出文件最多有两行。 第一行中仅有一个整数,表示从可可和卡卡家到学校需要的最短时间。第二行输出一个整数C,表示Ci之和

【样例输入】

6 7

1 21 3

2 61 5

1 31 1

3 41 1

4 61 1

5 61 2

1 51 4

【样例输出】

2

5

【数据范围】

   

2<=N<=500,1<=M<=124 750, 1<=ti, ci<=10 000

 

这题我用的是递归sap(),谁知道狂Wa。

大家用递归sap的时候想必经常会莫名NTR。

结论://dfs_sap()的Z正确性目前有待考证。。。

根据我的研究,经验总结如下:

1.退出条件:

-PS:有可能某次增广flow=0,但是改距离标号可以继续flow

-PS:有时候无限增广,输答案能看出上面的错误

2.修改距离标号:

-PS:距离标号最好直接+1,minj等手段极有可能造成≈没有距离标号优化的状况

3.dfs时的flow

-PS:一定要提前return,要不然改距离标号a~

4.重构图:

-PS:这样是质的差别,递归不卡时间?

5.唯一重点:

PS:实在不行时,去掉距离标号优化!另可T到死,不能WA到爆

6.用递归sap唯一的好处是省事……(什么你1分钟BFS_sap()?当我没说)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define MAXN (500+10)
#define MAXM (124750+10)
#define MAXCi (10000+10)
#define INF (2139062143)
#define For(i,n) for(int i=1;i<=n;i++)
#define Forp(p,u) for (int p=pre[u];p;p=next[p])
using namespace std;
int n,m,edge[2*MAXM],weight[2*MAXM],c[2*MAXM],next[2*MAXM],pre[MAXN],size=1;
void addedge(int u,int v,int w,int w2)
{
	edge[++size]=v;
	weight[size]=w;
	c[size]=w2;
	next[size]=pre[u];
	pre[u]=size;
}
int d[MAXN],q[MAXN*8];
void spfa()
{
	memset(d,127,sizeof(d));
	d[1]=0;
	int head=1,tail=1;q[1]=1;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[v]==INF||d[u]+weight[p]<d[v])
			{
				q[++tail]=v;d[v]=d[u]+weight[p];
			}
		}
		head++;
	}
}
int d2[MAXN],cnt[MAXN];
void spfa2()
{
	memset(d2,127,sizeof(d2));
	memset(cnt,0,sizeof(cnt));
	d2[n]=0;cnt[0]=1;
	int head=1,tail=1;q[1]=n;
	while (head<=tail)
	{
		int &u=q[head];
		Forp(p,u)
		{
			int &v=edge[p];
			if (d[u]-weight[p]!=d[v]) continue;
			if (d2[v]==INF)
			{
				q[++tail]=v;d2[v]=d2[u]+1;
				cnt[d2[v]]++;
			}
		}
		head++;
	}
}
bool sap_T=1,b[2*MAXM]={0};
int sap(int u,int flow)
{
	if (u==n) return flow;
	int tot=0,minj=INF;
	Forp(p,u)
	{
		int &v=edge[p];
	/*
		if (d2[v]==INF) continue;
		if (!(d[u]+weight[p]==d[v]||d[u]-weight[p]==d[v])) continue;
	*/
		if (!b[p]) continue;
		if (c[p]>0&&d2[u]==d2[v]+1)
		{
			int w=sap(v,min(flow-tot,c[p]));
			c[p]-=w;c[p^1]+=w;tot+=w;
			if (flow==tot) return tot;
		}else if (c[p]) minj=min(minj,d2[v]);
	}
	if (--cnt[d2[u]]==0)
		{
			d2[1]=n,sap_T=0;/*return tot;*/
		}//d2[1]=n+1;
//	if (minj^INF) cnt[d2[u]=minj+1]++;
/*	else*/ cnt[++d2[u]]++;
	return tot;
}
int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	memset(pre,0,sizeof(pre));
	scanf("%d%d",&n,&m);
	For(i,m)
	{
		int u,v,w1,w2;
		scanf("%d%d%d%d",&u,&v,&w1,&w2);
		addedge(u,v,w1,w2);
		addedge(v,u,w1,w2);
	}
	spfa();
//	for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl;
	cout<<d[n]<<endl;
	int ans=0;
	spfa2();
	int de_bug_1=0;
	For(i,n)
		Forp(p,i)
		{
			if (d[i]>d[edge[p]]) c[p]=0;
		//*0
		//	if (d2[i]!=INF&&d2[edge[p]]!=INF&&c[p]) cout<<i<<' '<<edge[p]<<endl,de_bug_1++;
			if (d[i]+weight[p]==d[edge[p]]) b[p]=b[p^1]=1,/*cout<<i<<' '<<edge[p]<<endl,*/de_bug_1++;
		}
//	cout<<de_bug_1<<endl;
	b[0]=1;
	For(i,n)
		Forp(p,i)
		{
			while (next[p]&&!b[next[p]]) next[p]=next[next[p]];
		}

	while(/*sap_T*/1)
	{
		if (d2[1]>=n) break;
		int w=sap(1,INF);
	//	if (!w) break;
//		cout<<ans<<' '<<d2[1]<<endl;
		ans+=w;
	}
	cout<<ans<<endl;
	return 0;
}

CF 237E(字母选取-费用流)

题目大意:有一字符串S,你需要从n个字符串中选取一些来拼出这个串,第i个字符串代价为i,限制取P次,问最小代价(无解输出-1)

建立超源S=0,超汇T=n+26+1 

1-n的结点为字符串 n+1-n+26的结点为字符

则可得——————————————————

从S向字符串连(最多可取数量),费用为i

从字符向T连(欲取数量)

从字符串向字符连(字符串可取该字母的数量)

得到图

跑费用……

!负数的布尔值为1.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (200+10)
#define M26 100
#define A 96
#define NONE (2139062143)
int map[MAXN][MAXN]={0},cost[MAXN][MAXN]={0},stf[M26]={0};
int start=0,end,n;
char s[5000];

int d[MAXN],pre[MAXN],q[MAXN*8];
bool b[MAXN];
void spfa()
{
	memset(b,0,sizeof(b));
	memset(d,127,sizeof(d));
	memset(q,0,sizeof(q));
	memset(pre,0,sizeof(pre));

	int head=1,tail=1;
	q[1]=start;b[start]=1;d[start]=0;
	while (head<=tail)
	{
		int now=q[head];
		for (int i=0;i<=end;i++)
		if (map[now][i]>0&&d[now]+cost[now][i]<d[i])
		{
			d[i]=d[now]+cost[now][i];
			pre[i]=now;
			if (!b[i])
			{
				q[++tail]=i;
				b[i]=1;
			}

		}

		b[now]=0;
		head++;
	}



}
void hllp()
{
	int totalcost=0;
	while (1)
	{
		spfa();
		if (d[end]==NONE) break;
		int flow=NONE,i=end;
		do
		{
			flow=min(flow,map[pre[i]][i]);
			i=pre[i];
		}while (i!=start);
		i=end;
		do
		{
			totalcost+=flow*cost[pre[i]][i];
			map[pre[i]][i]-=flow;
			map[i][pre[i]]+=flow;
			i=pre[i];
		}while (i!=start);

	}
	for (int i=end-27;i<end;i++)
	if (map[i][end])
	{
		cout<<"-1n";
		return;

	}
	cout<<totalcost<<endl;
}



int main()
{
//	freopen("c.in","r",stdin);
	scanf("%s",s);
	scanf("%d",&n);
	int len=strlen(s);
	for (int i=0;i<len;i++) stf[s[i]-A]++;
	end=n+27;
	for (int i=1;i<=26;i++) map[n+i][end]=stf[i];
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s);
		scanf("%d",&map[start][i]);
		memset(stf,0,sizeof(stf));
		for (int j=0;j<strlen(s);j++) stf[s[j]-A]++;
		for (int j=1;j<=26;j++) map[i][n+j]=stf[j];
		cost[0][i]=i;
		cost[i][0]=-cost[0][i];
	}
/*	for (int i=0;i<=end;i++)
		for (int j=0;j<=end;j++)
			if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/	hllp();
	cout<<'n';
/*	for (int i=0;i<=end;i++)
		for (int j=0;j<=end;j++)
			if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/
	return 0;
}

POJ 2195(多源多汇最小费用最大流)

这题 居然一次就过了^_^

Program P2195;
const
   maxn=200;
   maxm=200;
   maxh=200;
   maxd=1000;
var
   n,m,i,j,k,ut,vt:longint;
   s:string;
   form:array[1..maxn,1..maxm] of longint;
   u,v:array[1..maxh,1..2] of longint;

   map,f,cost:array[0..maxd,0..maxd] of longint;
   b:array[0..maxd] of boolean;
   q:array[1..maxd*5] of longint;
   d,pre:array[0..maxd] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure spfa;
var
   i,j,h,t,now:longint;
begin
   fillchar(d,sizeof(d),127);
   fillchar(b,sizeof(b),false);
   fillchar(pre,sizeof(pre),0);
   d[0]:=0;
   b[0]:=true;
   h:=1;t:=1;
   q[1]:=0;
   while h<=t do
   begin
      now:=q[h];
      for i:=0 to 2*ut+1 do
         if (map[now,i]-f[now,i]>0) then
            if (d[now]+cost[now,i]<d[i]) then
            begin
               d[i]:=d[now]+cost[now,i];
               pre[i]:=now;
               if not(b[i]) then
               begin
                  b[i]:=true;
                  inc(t);
                  q[t]:=i;
               end;
            end;

      b[now]:=false;
      inc(h);
   end;

end;
function hllp:longint;
var
   i,j,k,flow,totalcost,nowcost:longint;
begin
   hllp:=0;
   totalcost:=0;
   while (true) do
   begin
      spfa;
      if d[ut*2+1]=2139062143 then exit(totalcost);
      flow:=maxlongint;
      i:=ut*2+1;
      repeat
         flow:=min(map[pre[i],i]-f[pre[i],i],flow);
         i:=pre[i];
      until i=0;
      i:=ut*2+1;
      nowcost:=0;
      repeat
         inc(f[pre[i],i],flow);
         f[i,pre[i]]:=-f[pre[i],i];
         inc(nowcost,cost[pre[i],i]);
         i:=pre[i];

      until i=0;
      inc(totalcost,nowcost*flow);

   end;
end;
function main:longint;
var
   i,j,k:longint;
begin
   main:=0;
   fillchar(map,sizeof(map),0);
   fillchar(f,sizeof(f),0);
   fillchar(cost,sizeof(cost),0);
   for i:=1 to ut do map[0,i]:=1;
   for i:=ut+1 to ut+vt do map[i,ut+vt+1]:=1;
   for i:=1 to ut do
      for j:=ut+1 to ut+vt do
      begin
         map[i,j]:=1;
         cost[i,j]:=abs(u[i,1]-v[j-ut,1])+abs(u[i,2]-v[j-ut,2]);
         cost[j,i]:=-cost[i,j];
      end;
   main:=hllp;
end;
begin
   while not eof do
   begin
      readln(n,m);
      if (n=0) and (m=0) then break;
      ut:=0;
      vt:=0;
      for i:=1 to n do
      begin
         readln(s);
         for j:=1 to m do
            if s[j]='m'  then
            begin
               inc(ut);
               u[ut,1]:=i;
               u[ut,2]:=j;
            end
            else if s[j]='H' then
            begin
               inc(vt);
               v[vt,1]:=i;
               v[vt,2]:=j;
            end;
      end;
      writeln(main);

   end;
end.

POJ 2516(最小费用最大流)

一开始居然忘添反向边……

Program P2516;
const
   maxn=100;
   maxm=100;
   maxk=100;
var
   n,m,k,i,j,l,maxflow:longint;
   need,prod:array[1..maxn,1..maxk] of longint;
   needk,prodk:array[1..maxk] of longint;
   fee:array[1..maxk,1..maxn,1..maxm] of longint;

   cost,map,f:array[0..200,0..200] of longint;

   b:array[0..200] of boolean;
   d,pre:array[0..200] of longint;
   q:array[1..500000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure spfa;
var
   i,j,l,h,t,now:longint;
begin
   fillchar(d,sizeof(d),127);
   fillchar(b,sizeof(b),false);
   fillchar(pre,sizeof(pre),0);
   d[0]:=0;
   b[0]:=true;
   q[1]:=0;
   h:=1;t:=1;
   while h<=t do
   begin
      now:=q[h];
      for i:=0 to n+m+1 do
         if (map[now,i]-f[now,i]>0) then
            if (d[now]+cost[now,i]<d[i]) then
            begin
               d[i]:=d[now]+cost[now,i];
               pre[i]:=now;
               if not(b[i]) then
               begin
                  b[i]:=true;
                  inc(t);
                  q[t]:=i;
               end;
            end;


      b[now]:=false;
      inc(h);
   end;


end;
function hllp:longint;
var
   i,j,l,flow,totalflow,p:longint;
   totalcost,nowcost:longint;
begin
   hllp:=0;
   totalflow:=0;
   totalcost:=0;
   while (true) do
   begin
      spfa;
      if d[n+m+1]=2139062143 then exit(totalcost);
      flow:=maxlongint;
      i:=n+m+1;

      repeat
         flow:=min(flow,map[pre[i],i]-f[pre[i],i]);
         i:=pre[i];
      until i=0;

      nowcost:=0;
      i:=n+m+1;
      repeat
         inc(f[pre[i],i],flow);
         f[i,pre[i]]:=-f[pre[i],i];
         inc(nowcost,cost[pre[i],i]);
         i:=pre[i];
      until i=0;
      inc(totalcost,nowcost*flow);
   end;
end;
function main:longint;
var
   i,j,l,s,t:longint;
begin
   main:=0;
   for i:=1 to k do if prodk[i]<needk[i] then exit(-1);
   for i:=1 to k do
   begin
      fillchar(cost,sizeof(cost),0);
      fillchar(map,sizeof(map),0);
      fillchar(f,sizeof(f),0);
      s:=0;
      t:=n+m+1;
      for j:=1 to m do map[s,j]:=prod[j,i];
      for j:=1 to n do map[m+j,t]:=need[j,i];
      for j:=1 to m do
         for l:=1 to n do
         begin
            map[j,m+l]:=prod[j,i];
            cost[j,m+l]:=fee[i,l,j];
            cost[m+l,j]:=-cost[j,m+l];
         end;
      main:=main+hllp;

   end;

end;
begin
   while not seekeof do
   begin
      read(n,m,k);
      if (n=0) and (m=0) and (k=0) then break;

      fillchar(needk,sizeof(needk),0);
      fillchar(prodk,sizeof(prodk),0);

      for i:=1 to n do
         for j:=1 to k do
         begin
            read(need[i,j]);
            inc(needk[j],need[i,j]);
         end;
      for i:=1 to m do
         for j:=1 to k do
         begin
            read(prod[i,j]);
            inc(prodk[j],prod[i,j]);
         end;
      for i:=1 to k do
         for j:=1 to n do
            for l:=1 to m do
            begin
               read(fee[i,j,l]);
            end;
     writeln(main);



   end;
end.

POJ 1149(构图巨难……)

EK……

Program P1149;
var
   i,j,k,n,m,p:longint;
   map,f:array[0..500,0..500] of longint;
   visit,e,pre,pighouse:array[0..500] of longint;
   maxflow:longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure edmons_karp;
var
   i,j:longint;
   h,t:longint;
   queue:array[1..500] of longint;
begin
   maxflow:=0;

   while (true) do
   begin
      fillchar(pre,sizeof(pre),0);
      fillchar(e,sizeof(e),0);
      queue[1]:=0;
      e[0]:=maxlongint;
      h:=1;
      t:=1;
      while h<=t do
      begin
         for i:=1 to n+1 do
            if (map[queue[h],i]-f[queue[h],i]>0) and (e[i]=0) then
            begin
               e[i]:=min(e[queue[h]],map[queue[h],i]-f[queue[h],i]);
               pre[i]:=queue[h];
               inc(t);
               queue[t]:=i;
            end;
         if e[n+1]>0 then break;
         inc(h);
      end;

      if (e[n+1]=0) then break;

      i:=n+1;
      while (true) do
      begin
         inc(f[pre[i],i],e[n+1]);
         f[i,pre[i]]:=-f[pre[i],i];
         if i=0 then break;
         i:=pre[i];
      end;
      inc(maxflow,e[n+1]);
   end;

end;
begin
   read(m,n);
   fillchar(visit,sizeof(visit),0);
   fillchar(f,sizeof(f),0);
   fillchar(map,sizeof(map),0);
   fillchar(e,sizeof(e),0);


   for i:=1 to m do read(pighouse[i]);
   for i:=1 to n do
   begin
      read(k);
      for j:=1 to k do
      begin
         read(p);
         if (visit[p]=0) then
         begin
            map[0,i]:=map[0,i]+pighouse[p];
            visit[p]:=i;
         end
         else
         begin
            map[visit[p],i]:=maxlongint;
         end;
      end;
      read(p);
      map[i,n+1]:=p;

   end;

   edmons_karp;
   writeln(maxflow);

end.

POJ 1273(网络流-附hllp+sap模板)

网络流入门题目

Program P1273;
Var
   n,m,i,j,x,y,p,level:longint;
   map,f:array[1..400,1..400] of longint;
   list:array[0..400,0..400] of longint;
   queue:array[1..400] of longint;
   b:array[1..400] of boolean;
   d,e:array[1..400] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure dijstra;
var
   h,t,i:longint;
begin
   queue[1]:=n;
   b[n]:=true;
   h:=1;
   t:=1;
   while h<=t do
   begin
      for i:=1 to n-1 do
         if (map[i,queue[h]]>0) and (not(b[i])) then
         begin
            inc(t);
            queue[t]:=i;
            b[i]:=true;
            d[i]:=d[queue[h]]+1;
         end;
      inc(h);
   end;
   d[1]:=n+1;
end;
procedure push(i,j:longint);
var
   flow:longint;
begin
   flow:=min(map[i,j]-f[i,j],e[i]);

   if (e[j]=0) and (j<>1) and (j<>n) then
   begin
      inc(list[d[j],0]);
      list[d[j],list[d[j],0]]:=j;
      level:=max(level,d[j]);
   end;

   dec(e[i],flow);
   inc(e[j],flow);
   inc(f[i,j],flow);
   f[j,i]:=-f[i,j];
end;
procedure relable(i:longint);
var
   j,minj:longint;
begin
   minj:=maxlongint;
   for j:=1 to n do
      if (map[i,j]-f[i,j]>0) and (b[j]) then
         minj:=min(minj,d[j]);
   d[i]:=minj+1;

   level:=d[i];
   list[level,0]:=1;
   list[level,1]:=i;
end;
procedure sa;
var
   i,j,minj:longint;
   tag:boolean;
begin
   dijstra;
   level:=0;
   for i:=1 to n do
      if (map[1,i]>0) and (b[i]) then
      begin
         dec(e[1],map[1,i]);
         inc(e[i],map[1,i]);
         inc(f[1,i],map[1,i]);
         f[i,1]:=-f[1,i];
         inc(list[d[i],0]);
         list[d[i],list[d[i],0]]:=i;
         level:=max(level,d[i]);
      end;
   while (level>0) do
   begin
      i:=list[level,list[level,0]];
      dec(list[level,0]);
      while (level>0) and (list[level,0]=0) do dec(level);

      for j:=1 to n do
         if (map[i,j]-f[i,j]>0) and (d[i]=d[j]+1) and (b[j]) then
         begin
            push(i,j);
            if e[i]=0 then break;
         end;
      if e[i]>0 then relable(i);
   end;
end;
begin
   while not eof do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(f,sizeof(f),0);
      fillchar(d,sizeof(d),0);
      fillchar(b,sizeof(b),false);
      fillchar(list,sizeof(list),0);
      fillchar(e,sizeof(e),0);
      readln(m,n);
      for i:=1 to m do
      begin
         readln(x,y,p);
         inc(map[x,y],p);
      end;
      sa;
      writeln(e[n]);
   end;
end.

Sap:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAXN (200000+10)
#define MAXNnode (200000+10)
#define MAXedge (200000+10)
#define INF (2139062143)
int n,m,size,edge[MAXedge],pre[MAXNnode],next[MAXedge],weight[MAXedge],s,t;
int un(int p){return (p%2)?(p+1):p-1;}
void addedge(int u,int v,int w)
{
     edge[++size]=v;weight[size]=w;
     next[size]=pre[u];pre[u]=size;
     edge[++size]=u;weight[size]=0;
     next[size]=pre[v];pre[v]=size;
}
int q[MAXN*10],d[MAXN*2],pre2[MAXN],cnt[MAXN];
void spfa()
{
    int head=1,tail=1;
    memset(d,127,sizeof(d));
    q[1]=t;d[t]=0;
    while (head<=tail)
    {
        int &u=q[head];
        for (int p=pre[u];p;p=next[p])
        {
            int &v=edge[p];
            if (d[v]>d[u]+1)
            {
               d[v]=d[u]+1;
               q[++tail]=v;
               cnt[d[v]]++;
            }
        }
        head++;
    }

}
int relable(int u)
{
    int minj=n;
    for (int p=pre[u];p;p=next[p])
        if (weight[p]&&d[edge[p]]!=INF) minj=min(minj,d[edge[p]]+1);
    return minj;
}
long long sap()
{
     spfa();
     int now=s;
	 long long nowflow=INF,maxflow=0;
     while (1)
     {
         int flag=0;
         for (int p=pre[now];p;p=next[p])
         {
             int &v=edge[p];
             if (weight[p]&&d[v]==d[now]-1)
             {
                 flag=v;
                 pre2[v]=p;
                 now=v;
                 break;
             }
         }
         if (flag)
         {
            if (now==t)
            {
               nowflow=INF;
               for (int p=now;p!=s;p=edge[un(pre2[p])])
                   nowflow=min(nowflow,(long long )weight[pre2[p]]);
               maxflow+=nowflow;
               for (int p=now;p!=s;p=edge[un(pre2[p])])
               {
                   weight[pre2[p]]-=nowflow;
                   weight[un(pre2[p])]+=nowflow;
               }
               now=s;
               memset(pre2,0,sizeof(pre2));
            }
         }
         else
         {
             if (--cnt[d[now]]==0) break;
             d[now]=relable(now);
             cnt[d[now]]++;
             if (now!=s) now=edge[un(pre2[now])];
     	}
     }
     return maxflow;
}
int main()
{
	while (scanf("%d%d",&m,&n)==2)
	{
	    memset(pre,0,sizeof(pre));
	    memset(next,0,sizeof(next));
	    memset(edge,0,sizeof(edge));
	    memset(weight,0,sizeof(weight));
    	    memset(cnt,0,sizeof(cnt));
	    size=0; s=1;t=n;
            for (int i=1;i<=m;i++)
	    {
    	        int u,v,w;
        	cin>>u>>v>>w;
  	        addedge(u,v,w);
    	    }
        if (m==0) cout<<'0'<<endl;
	    else cout<<sap()<<endl;
	}
	return 0;
}

POJ 1325(2部图匹配)

2部图匹配,不能考虑0

Program P1325;
var
   n,m,k,i,j:longint;
   p,x,y,level:longint;
   map,f,list:array[-1..300,-1..300] of longint;
   d,e:array[-1..300] of longint;
   queue:array[1..300] of longint;
   b:array[-1..300] of boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure dijstra;
var
   h,t,i:longint;
begin
   fillchar(d,sizeof(d),0);
   fillchar(queue,sizeof(queue),0);
   fillchar(b,sizeof(b),false);
   queue[1]:=n+m;
   b[n+m]:=true;
   h:=1;
   t:=1;
   while h<=t do
   begin
      for i:=-1 to n+m-1 do
      begin
         if (map[i,queue[h]]>0) then
            if (not(b[i])) then
         begin
            inc(t);
            queue[t]:=i;
            b[i]:=true;
            d[i]:=d[queue[h]]+1;
         end;
      end;
      inc(h);
   end;
   d[-1]:=n+m+2+1;
end;
procedure push(i,j:longint);
var
   flow:longint;
begin
   flow:=min(e[i],map[i,j]-f[i,j]);

   if (e[j]=0) and (j>-1) and (j<n+m) then
   begin
      inc(list[d[j],0]);
      list[d[j],list[d[j],0]]:=j;
      level:=max(level,d[j]);
   end;

   dec(e[i],flow);
   inc(e[j],flow);
   inc(f[i,j],flow);
   f[j,i]:=-f[i,j];

end;
procedure relable(i:longint);
var
   j,minj:longint;
begin
   minj:=maxlongint;
   for j:=-1 to n+m do
      if (map[i,j]-f[i,j]>0) and (b[j]) then minj:=min(minj,d[j]);
   d[i]:=minj+1;

   level:=d[i];
   inc(list[level,0]);
   list[level,1]:=i;
end;
Procedure hllp;
var
   i,j,flow:longint;
begin
   dijstra;

   level:=0;
   for i:=0 to n-1 do
      if b[i] then
      begin
         e[i]:=1;
         f[-1,i]:=1;
         f[i,-1]:=-1;


         inc(list[d[i],0]);
         list[d[i],list[d[i],0]]:=i;
         level:=max(level,d[i]);
      end;
   while (level>0) do
   begin
      i:=list[level,list[level,0]];
      dec(list[level,0]);
      while (level>0) and (list[level,0]=0) do dec(level);

      for j:=-1 to n+m do
         if (d[i]=d[j]+1) and (map[i,j]-f[i,j]>0) and (b[j]) then
         begin
            push(i,j);

            if e[i]=0 then break;
         end;
      if e[i]>0 then relable(i);

   end;

end;
begin
   read(n);
   while (n>0) do
   begin
      fillchar(list,sizeof(list),0);
      fillchar(e,sizeof(e),0);
      fillchar(f,sizeof(f),0);

      read(m,k);
      fillchar(map,sizeof(map),0);
      for i:=1 to k do
      begin
         read(p,x,y);
         if (x=0) or (y=0) then continue;
         map[x,n+y]:=1;
      end;
      for i:=0 to n-1 do map[-1,i]:=1;
      for i:=n to n+m-1 do map[i,n+m]:=1;
      hllp;
      writeln(e[n+m]);

      read(n);

   end;
end.

POJ 1459(预留推进)

hllp写到最后写成预留推进了……

Program P1459;
var
   n,np,nc,m,i,j,src,t,level:longint;
   ch:char;
   s:string;
   d,e,pre:array[-1..100] of longint;
   map,f:array[-1..100,-1..100] of longint;
   queue:array[1..102] of longint;
   list:array[0..103,0..102] of longint;
   b:array[-1..100] of boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure hllp;
var
   i,j,maxflow,flow,minj:longint;
   h,t:longint;
   tag:boolean;
begin
   level:=0;
   maxflow:=0;
   flow:=0;
   h:=1;
   t:=1;
   queue[h]:=n;
   while h<=t do
   begin
      for i:=0 to n-1 do
         if (map[i,queue[h]]>0) and (not(b[i])) then
         begin
            inc(t);
            queue[t]:=i;
            d[i]:=d[queue[h]]+1;
            b[i]:=true;
         end;
      inc(h);
   end;
   d[-1]:=n+2;
   {
   for i:=0 to n-1 do
      if e[i]>0 then
      begin
         inc(list[d[i],0]);
         list[d[i],list[d[i],0]]:=i;
         level:=max(level,d[i]);
      end;
   }
   while (true) do
   begin
      i:=n;
      for j:=0 to n-1 do
      begin
         if (e[j]>0) and (d[j]>d[i]) then i:=j;
      end;
      if i=n then break;
 {     i:=list[level,list[level,0]];
      dec(list[level,0]);
      while (level>0) and (list[level,0]=0) do dec(level);
      }

      tag:=false;
      for j:=-1 to n do
      begin
         if e[i]=0 then break;
            if (d[i]=d[j]+1) and (map[i,j]-f[i,j]>0) then
            begin
               tag:=true;
               flow:=min(map[i,j]-f[i,j],e[i]);
               dec(e[i],flow);
               inc(e[j],flow);
               inc(f[i,j],flow);
               f[j,i]:=-f[i,j];
            end;
      end;
      if (e[i]>0) then
      begin
         minj:=maxlongint;
         for j:=-1 to n do
            if (map[i,j]-f[i,j]>0) {and (d[i]>=d[j])} then minj:=min(minj,d[j]);
        { if minj=maxlongint then
         begin
            e[i]:=0;
            continue;
         end;    }
         d[i]:=minj+1;
      end;

   end;

end;
function isdight(a:char):boolean;
begin
   if (48<=ord(a)) and (ord(a)<=57) then exit(true) else exit(false);
end;
procedure rea(var a:longint);
var
   ch:char;
   s:string;
begin
   ch:=' ';
   while not(isdight(ch)) do read(ch);
   s:='';
   repeat
      s:=s+ch;
      read(ch);
   until not(isdight(ch));
   val(s,a);
end;
begin
{   assign(input,'p1459.in');
   assign(output,'p1459.out');
   reset(input);
   rewrite(output);                    }
   while not seekeof do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(e,sizeof(e),0);
      fillchar(f,sizeof(f),0);
      fillchar(list,sizeof(list),0);
      fillchar(d,sizeof(d),0);
      fillchar(b,sizeof(b),false);
      rea(n);
      for i:=-1 to n do pre[i]:=i;
      rea(np);
      rea(nc);
      rea(m);
      for i:=1 to m do
      begin
        rea(src);
        rea(t);
        rea(map[src,t]);
      end;
      for i:=1 to np do
      begin
        rea(t);
        rea(map[-1,t]);
        e[t]:=map[-1,t];
        f[-1,t]:=map[-1,t];
        f[t,-1]:=-map[-1,t];
      end;
      for i:=1 to nc do
      begin
         rea(src);
         rea(map[src,n]);
      end;

      hllp;
      writeln(e[n]);
   end;
{   close(input);
   close(output);     }
end.