【wikioi】1028花店橱窗布置

//暴力搜索
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 110
int d[MAX][MAX];int f,v;int lie[MAX];int vis[MAX];
int ds(int dep)
{//如果dep达到 f 则自动跳出/*如果没有遍历搜索每一种可能如果满足要求，开始下一层递归*/int i,j,k;int r;int x,y;if(dep==f){r=0;for(i=1;i<=f;i++){x=i,y=lie[i];r+=d[x][y];}return r;}else{int max=0;for(i=1;i<=v;i++){if(vis[i]==-1){vis[i]=0;lie[dep+1]=i;k=ds(dep+1);if(k>max)max=k;vis[i]=-1;}}return max;}
}
int main(void)
{freopen("in.txt","r",stdin);int i,j,k;memset(lie,0,sizeof(lie));memset(vis,-1,sizeof(vis));scanf("%d%d",&f,&v);for(i=1;i<=f;i++){for(j=1;j<=v;j++){scanf("%d",&d[i][j]);}}printf("%d\n",ds(0));return 0;
}

#include <stdio.h>
#include <string.h>
#define max(x, y) ((x)>(y) ? (x):(y))
#define min(x, y) ((x)<(y) ? (x):(y))
#define N_MAX 200typedef unsigned char bool;int F, V;
int W[N_MAX][N_MAX];
int Lx[N_MAX];
int Ly[N_MAX];
int left[N_MAX];
bool S[N_MAX], T[N_MAX];
bool b[N_MAX][N_MAX];
bool match(int);
void update();
void KM();int main()
{unsigned long long int ans=0;int i, j;scanf("%d %d", &F, &V);for (i=1;i<=F;i++)for (j=1;j<=V;j++)scanf("%d", &W[i][j]);KM();for (i=1;i<=V;i++)if (b[left[i]][i]==0){ans+=W[left[i]][i];b[left[i]][i]=1;}printf("%llu\n", ans);return 0;
}
bool match(int i)
{int j;S[i]=1;for (j=1;j<=V;j++)if (Lx[i]+Ly[j]==W[i][j] && !T[j]){T[j]=1;if (!left[j] || match(left[j])){left[j]=i;return 1;}}return 0;
}
void update()
{int a=1<<30;int i, j;for (i=1;i<=F;i++)		if (S[i])for (j=1;j<=V;j++)	if (!T[j])a=min(a, Lx[i]+Ly[j]-W[i][j]);for (i=1;i<=V;i++){if (S[i])		Lx[i]-=a;if (T[i])		Ly[i]+=a;}return ;
}
void KM()
{int i, j;memset(left, 0, sizeof(left));memset(Lx, 0, sizeof(Lx));memset(Ly, 0, sizeof(Ly));for (i=1;i<=F;i++)for (j=1;j<=V;j++)Lx[i]=max(Lx[i], W[i][j]);for (i=1;i<=F;i++){for ( ; ; ){for (j=1;j<=V;j++)	S[j]=T[j]=0;if (match(i))	break;	else	update();}}return ;
}