CH 白色情人节1(②第一天-KM算法)

背景

下过雨的夏天傍晚 我都会期待
唱歌的蝉 嘿 把星星都吵醒 月光晒了很凉快
就是这样回忆起来 第一次告白
尴尬的我 看 爱装得很哲学的你其实很可爱
你说活在明天 活在期待 不如活得今天很自在
我说我懂了 会不会太快 未来 第一天要展开

描述

时间回溯到男女主认识的第一天——女主同学举办的联谊会,男主迟到了那天的联谊会,而男主到达现场时女主也刚好没有男伴,这就是他们的第一次相遇。
男主回想起来不禁一阵感慨(为啥这么好的妹子你们都不搭讪呢),突然男主想到,如果当时已经配对的n对男女好感值之和不是最大,会不会自己就遇不上女主了呢?

输入格式

第一行两个正整数n和queen,表示已有n对男女可以配对和女主的编号queen。(男编号为X1~Xn,女编号为Y1~Yn+1)
接下来n*(n+1)行,每行三个正整数Xi,Yi,Zi,表示男Xi女Yi之间的好感度为Zi保证每对(Xi,Yi)没有重复,即两人的关系至多一条
不存在男与男、女与女之间的好感度!

输出格式

前n行输出联谊会上n对男女的配对情况(会多出来一名女生),每行两个正整数Xi和Yi(空格隔开),任意一种符合条件的方案均可。
第n+1行,对于你输出的方案,如果女主未配对,输出"YES"(不含引号),表示女主会遇到男主,否则输出"NO"(不含引号)。

样例输入

2 3
1 1 15
1 2 20
1 3 17
2 1 22
2 2 14
2 3 14

样例输出

1 2
2 1
YES

数据范围与约定

对于100%的数据,1leq nleq 520,1leq Z_{i}leq 201314

样例解释

如图,已经配对的关系有是男1号女2号男2号女1号

来源

*****关系~

km算法

就是二分图匹配时维护lx[i],ly[i]

满足

1.对于任意边lx[i]+ly[i]>=w[i,j]

2.如果存在一组匹配,其中任意边满足lx[i]+ly[i]=w[i,j],它一定是最大匹配(如果随意调换一边,必然出现lx[i]+ly[j]+lx[i']+ly[j']=w[i,j]+w[i',j']≥w[i,j']+w[i',j]

于是每次找出slock,表示对所有找过的i,不为0的min(lx[i]+ly[j]-w[i,j])

把slock的值从左移至右,既不改变原图能走的边,又能使图得到扩充。

//一开始应该把lx[i]设成max(w[i,j],0),ly[i]设成0

每次扩充必须保证图中的边满足lx[i]+ly[i]=w[i,j],否则用slock扩充


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
using namespace std;
#define INF (100000000)
#define MAXN (520+10)
#define MAXWi (201314)
int n,m,yi,slack;
int w[MAXN][MAXN],lx[MAXN],ly[MAXN],a[MAXN];//a=?->yi
bool vx[MAXN],vy[MAXN];
bool find(int x)
{
	vx[x]=1;
	for (int i=1;i<=m;i++)
		if (!vy[i])
		{
			int t=lx[x]+ly[i]-w[x][i];
			if (t==0)
			{
				vy[i]=1;
				if (a[i]==0||find(a[i])) {a[i]=x;return 1;}
			}else slack=min(slack,t);
		}
	return 0;
}
int main()
{
//	freopen("input","r",stdin);
	scanf("%d%d",&n,&yi);m=n+1;
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	memset(a,0,sizeof(a));
	for (int i=1;i<=n*(n+1);i++)
	{
		int u,v,wei;scanf("%d%d%d",&u,&v,&wei);w[u][v]=wei;
		lx[u]=max(lx[u],wei);
	}
	for (int i=1;i<=n;i++)
	{
		memset(vx,0,sizeof vx);
		memset(vy,0,sizeof vy);
		slack=INF;
		while (!find(i))
		{
			for (int j=1;j<=n;j++) if (vx[j]) lx[j]-=slack;
			for (int j=1;j<=m;j++) if (vy[j]) ly[j]+=slack;
			memset(vx,0,sizeof vx);
			memset(vy,0,sizeof vy);
			slack=INF;
		//	find(i);
		}
	}
	for (int i=1;i<=m;i++)
	{
		if (a[i]) printf("%d %dn",a[i],i);
	}
	if (a[yi]) printf("NOn");
	else printf("YESn");
	return 0;
}

BZOJ 2547(匈牙利算法-任意边的处理)

2547: [Ctsc2002]玩具兵

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 104  Solved: 50
[Submit][Status][Discuss]

Description

小明的爸爸给他买了一盒玩具兵,其中有 K个步兵,K个骑兵和一个天兵,个个高大威猛,形象逼真。盒子里还有一个M*N棋盘,每个格子(i,j)都有一个高度Hij,并且大得足以容纳所有的玩具兵。小明把所有的玩具兵都放到棋盘上去,突然想到了一种很有趣的玩法:任意挑选T个不同的格子,并给每个格子i规定一个重要值Ri­­,游戏的目标就是每次沿东南西北之一的方向把一个玩具兵移动到其相邻的格子中(但不能移动到棋盘外面去),最终使得每个挑选出的格子i上恰好有Ri个玩具兵。小明希望所有的玩具兵都在某个选定的格子中,因此他总是使选出的T个格子的重要值之和等于玩具兵的个数。为了增加难度,小明给玩具兵们的移动方式做了一些规定:

  步兵只会往高处爬,因此如果两个格子AB相邻,当且仅当格子A的高度小于或等于B,步兵才可以从A移动到B

      骑兵只会往低处跳,因此如果两个格子AB相邻,当且仅当格子A的高度大于或等于B,骑兵才可以从A移动到B

      天兵技术全面,移动不受任何限制。

       可是没玩几次,小明就发现这个游戏太难了,他常常玩了好半天也达不到目的。于是,他设计了一种“超能力”,每使用一次超能力的时候,虽然不能移动任何一个玩具兵,但可对它们进行任意多次交换操作,每次交换两个玩具兵。等这次超能力使用完后又可和平常一样继续移动这些玩具兵。借助强大的超能力,这个游戏是容易玩通的,但是怎样才能让使用超能力的次数最少呢?

 

Input

第一行包含四个整数:M,N,K,T (2<=M,N<=100, 1<=K<=50, 1<=T<=2K+1)

    第二行包括2K+1个数对(xi,yi),代表各个玩具兵的初始位置。前K个代表兵,接下来的K个代表骑兵,最后一个代表兵。

    第三行包含T个三元组(xi,yi,ri),第i组代表第i个目标格的位置和重要值。

        以下M行,每行N个整数。其中第i行第j个数为即格子的高度Hij。高度是不超过100的正整数,注意:不同玩具兵的初始位置可能相同。输入数据保证无错,选定的T个格子的重要值之和保证等于2K+1

Output

仅包含一行,即使用超能力的最小次数T

Sample Input

4 6 2 5

1 1 1 5 4 1 4 5 3 3

1 2 1 2 6 1 3 2 1 3 6 1 4 3 1

3 2 6 1 3 5

2 1 7 4 4 6

2 3 1 4 3 4

4 3 4 3 2 3

Sample Output

1

先来分析一下这个问题。
1.显然天兵的初始位置不重要。
2.最坏情况不断使用天兵,2*k次便能解决.

不妨假设不存在天兵:
1.我们把调换位置-改为调换兵种(显然成立),那么一个棋子一定调换(否则移到需要的位置调换).
2.显然如果我有确定的‘超能力’次数,那么任何一个棋子所能到达的地方有限(bfs)。
3.显然我们可以判断1个棋子在超能力步数内必须到达另一个棋子(就是这个棋子,无论怎么调换兵种).
问是否是合法方案   
那么这就是一个二分图匹配,必须完全匹配。

天兵的意义
1.显然一个天兵可以在棋盘上随便走,在每次调换时,找一个棋子把它挪到目的地
   这相当于在二分图上任意填‘超能力次数’条边。
故先算出最大匹配数,再+超能力数,可以得到最优方案

模型建毕:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN (100+10)
#define MAXM (100+10)
#define MAXK (100+10)
#define MAXT (100+1+10)
#define COST (bool(type)^(f[x][y]&1))?(h[x][y]<h[x+path[i][0]][y+path[i][1]]):(h[x][y]>h[x+path[i][0]][y+path[i][1]])
const int path[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m,k,t,h[MAXM][MAXN],f[MAXM][MAXN];
queue< pair<int,int> > q;
bool inside(int x,int y)
{
	if (1<=x&&x<=m&&1<=y&&y<=n) {/*cout<<'A'<<x<<' '<<y<<endl;*/ return 1;}else return 0;
}
void bfs(bool type,int x,int y)  //type-> 0 upper 1 lower
{
	memset(f,127,sizeof(f));
	f[x][y]=0;
	q.push(make_pair(x,y));
	while (!q.empty())
	{
		pair<int ,int> now=q.front();
		int &x=now.first,&y=now.second;
		for (int i=0;i<4;i++)
		{
			int c=COST;
			if (inside(x+path[i][0],y+path[i][1]))
				if (f[x+path[i][0]][y+path[i][1]]>f[x][y]+c)
			{
		//		cout<<(x+path[i][0])<<' '<<(y+path[i][1])<<endl;
				f[x+path[i][0]][y+path[i][1]]=f[x][y]+c;
				q.push(make_pair(x+path[i][0],y+path[i][1]));
			}
		}
		q.pop();
	}
}
pair<int,int> A[MAXT],B[MAXT];
int cost[MAXK][MAXT],a[MAXT];
bool b[MAXT];
bool find(int x,int maxcost)
{
	for (int i=1;i<=2*k+1;i++)
		if (!b[i]&&cost[x][i]<=maxcost)
		{
			b[i]=1;
			if (a[i]==0) {a[i]=x;return 1;	}
			if (find(a[i],maxcost)) {a[i]=x; return 1;	}
		}
	return 0;
}
int hopcroft(int maxcost)
{
	memset(a,0,sizeof(a));
	int ans=0;
	for (int i=1;i<=2*k;i++)
	{
		memset(b,0,sizeof(b));
		if (find(i,maxcost)) ans++;
	}
//	cout<<ans<<endl;
	return ans;
}
int b_search()
{
	int l=0,r=2*k;
	while (l<r)
	{
		m=(l+r)>>1;
		if (hopcroft(m)+m>=2*k) r=m;
		else l=m+1;
	}
	return l;
}
int main()
{
//	freopen("2547.in","r",stdin);
	scanf("%d%d%d%d",&m,&n,&k,&t);
	for (int i=1;i<=2*k+1;i++) scanf("%d%d",&A[i].first,&A[i].second);
	int size=1;
	for (int i=1;i<=t;i++)
	{
		int r;
		scanf("%d%d%d",&B[size].first,&B[size].second,&r);
		size++;
		for (r--;r;r--,size++) B[size]=B[size-1];
	}
	for (int i=1;i<=m;i++)
		for (int j=1;j<=n;j++)
			scanf("%d",&h[i][j]);

/*	bfs(1,1,2);
	for (int i=1;i<=m;i++)
	{
		for (int j=1;j<=n;j++) cout<<f[i][j]<<' ';
		cout<<'n';
	}
*/
	for (int i=1;i<=2*k;i++)
	{
		bfs((i>k),A[i].first,A[i].second);
		for (int j=1;j<=2*k+1;j++)
		{
			cost[i][j]=f[B[j].first][B[j].second];
//			cout<<i<<' '<<j<<' '<<cost[i][j]<<endl;
		}
	}

	cout<<b_search()<<endl;


	return 0;
}

POJ 3692(匈牙利算法)

匈牙利算法:

b[]保存当前找交错路P的各点是否已被连通,a[]表示某点之前的点

本题的2分图是取最大团(各点互相连通),利用2分图性质,可看成补图的最大独立集(各点互不连通)……

Program P3692;
const
   maxn=200;

var
   n,m,l,i,j,k,ans,x,y:longint;
   b:array[1..400] of boolean;
   map:array[1..400,1..400] of boolean;
   a:array[1..400] of longint;
function find(x:longint):boolean;
var
   i,j:longint;
begin
   for i:=1 to m do
      if not(b[i]) and (map[x,i]) then
      begin
         b[i]:=true;
         if a[i]=0 then begin a[i]:=x; exit(true); end;
         if find(a[i]) then begin a[i]:=x; exit(true); end;
      end;

   exit(false);
end;
begin
   i:=1;
   read(n,m,l);
   while (n+m+l>0) do
   begin
      ans:=0;
      fillchar(a,sizeof(a),0);
      fillchar(map,sizeof(map),true);
      for k:=1 to l do
      begin
         read(x,y);
         map[x,y]:=false;
      end;
      for k:=1 to n do
      begin
         fillchar(b,sizeof(b),false);
         if find(k) then inc(ans);
      end;
      writeln('Case ',i,': ',n+m-ans);
      inc(i);
      read(n,m,l);
   end;
end.