A - 奔小康赚大钱
题意：
求解二分图的最优匹配
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return 0;
}
B - Going Home
题意:
给你一个N行M列的矩阵，其中“.”代表空地，“H”代表房子，“m”代表人，其中有n个房子和n个人。现在要求每个人进入一间房子，且人走一步需要支付1美元。
求最小需要花费多少美元才能让所有人都进入到房子中（每个人只能进入一间房子，每个房子只能容纳一个人）。
题解:
每个人都与每个房间连接一条边,边权为水平距离加竖直距离,然后得到一个二分图,对这个二分图运用KM算法.
#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int N;
struct Node
{
int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
int n,m,sum1,sum2;
char c;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
sum1=0;
sum2=0;
getchar();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
c=getchar();
if(c=='m')
{
xc[sum1].x=i;
xc[sum1++].y=j;
}
else if(c=='H')
{
yc[sum2].x=i;
yc[sum2++].y=j;
}
}
c=getchar();
}
for(int i=0;i<sum1;i++)
{
for(int j=0;j<sum2;j++)
{
love[i][j]=-abs(xc[i].x-yc[j].x)-abs(xc[i].y-yc[j].y);
}
}
N=sum1;
printf("%d\n",-KM());
}
return 0;
}
C - Interesting Housing Problem
题意:
现在有1所学校，N个学生,M个公寓，还有一个R值，代表学生对该公寓的满意度，如果为正数，越高表示越喜欢住在该所公寓，0表示不喜欢也不讨厌（意思就是可以住），如果为负数则代表不喜欢住，也不能住（要不小心起义~）。现在校长想让所有学生的满意度最高，而且学生跟公寓是一一对应的，另外，学生也不能入住那些没对公寓进行评价的。
求出最大值。
题解:
#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 510;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int n,m;
struct Node
{
int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < m; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < n; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < m; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < n; ++i) {
fill(slack, slack + m, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < m; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
if(d==INF) return -1; //无法松弛,找不到完备匹配
for (int j = 0; j < n; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
}
for (int j = 0; j < m; ++j) {
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 防止匹配到不存在的边
int res = 0,flag=0;
for(int i = 0; i < m; i++){
if(match[i]==-1||love[match[i]][i]==-INF)
continue;
res += love[match[i]][i];
flag++;
}
if(flag<n) res=-1;
return res;
}
int main()
{
int a,b,c,e,cas=1;
while(scanf("%d%d%d",&n,&m,&e)!=EOF){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
love[i][j]=-INF;
for(int i=0;i<e;i++) {
scanf("%d%d%d",&a,&b,&c);
if(c<0) continue;
love[a][b]=c;
}
printf("Case %d: %d\n",cas++,KM());
}
return 0;
}
D - Special Fish
题意:
武大荷塘有N条鱼(不分性别),每条鱼有一个价值vi.且给出一个N*N的矩阵,矩阵中(i,j)格为1表示,第i条鱼会攻击第j条鱼并产下卵.
产卵的数量= vi XOR vj. 现在每条鱼只能被攻击1次(一条鱼只能攻击1次且被攻击1次),且每条鱼只会攻击它可能会攻击的所有鱼中的一条(哪些其他鱼它会攻击已经在N*N矩阵中给出).现在要你求这N条鱼产卵数目的最大值.
题解:
#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
int val[MAXN];
int N;
struct Node
{
int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每个男生的期望值为0
// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大
while (1) {
// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到归宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while(scanf("%d",&N)!=EOF,N)
{
for(int i=0;i<N;i++)
scanf("%d",val+i);
memset(love,0,sizeof(love));
char c;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
scanf(" %c",&c);
if(c=='1')
{
love[i][j]=val[i]^val[j];
}
}
}
printf("%d\n",KM());
}
return 0;
}
S - Ants
题意:
跟B题差不多,给定n个虫的坐标和m颗树的坐标(m>n),n个从要搬迁到树中,每棵树只能住一个虫。求出搬迁的最短距离。
题解:
两点距离直接算就可以了,虫树两两之间连边,权值可能是小数,所以要控制浮点误差eps
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
double love[MAXN][MAXN],slack[MAXN];
int match[MAXN],ans[MAXN];
int visb[MAXN],visg[MAXN];
double eb[MAXN],eg[MAXN];
int n;
double eps=1e-10;
bool DFS(int girl)
{
visg[girl]=true;
for(int boy=1;boy<=n;boy++)
{
if(visb[boy]) continue;
double gap=abs(eb[boy]+eg[girl]-love[girl][boy]);
if(gap<=eps)
{
visb[boy]=1;
if(match[boy]==-1||DFS(match[boy]))
{
match[boy]=girl;
return true;
}
}
else slack[boy]=min(slack[boy],gap);
}
return false;
}
void km()
{
memset(match,-1,sizeof(match));
memset(eb,0,sizeof(eb));
for(int i=1;i<=n;i++)
{
eg[i]=love[i][1];
for(int j=2;j<=n;j++)
{
eg[i]=max(eg[i],love[i][j]);
}
}
for(int i=1;i<=n;i++)
{
fill(slack+1,slack+1+n,INF);
while(true)
{
memset(visg,0,sizeof(visg));
memset(visb,0,sizeof(visb));
if(DFS(i)) break;
double d=INF;
for(int i=1;i<=n;i++)
{
if(!visb[i]) d=min(d,slack[i]);
}
for(int i=1;i<=n;i++)
{
if(visg[i]) eg[i]-=d;
if(visb[i]) eb[i]+=d;
else slack[i]-=d;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d\n",match[i]);
}
}
double dist(pair<double,double> p1,pair<double,double> p2)
{
return -sqrt((p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second));
}
pair<double,double> worm[MAXN];
pair<double,double> tree[MAXN];
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&worm[i].first,&worm[i].second);
}
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&tree[i].first,&tree[i].second);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
love[i][j]=dist(tree[i],worm[j]);
}
}
km();
}
}
E - Chocolate
题意:
有n个盒子组成一个圆，盒子总共有不超过n个蛋糕，有的有多于1个，有的为0。可以将一个盒子里的蛋糕往左右两个盒子里移动，一次只能移动一个，使最终每个盒子里有不超过一个蛋糕（可以没有），求最小的移动数
题解:
要使得每个盒子的蛋糕最多为一个,那么那些多于一个蛋糕的蛋糕盒里的蛋糕只能移向没有蛋糕的蛋糕盒;也就是多出的蛋糕和空蛋糕盒构成二分图,他们的距离为蛋糕盒之间的距离,由于是排列是圆形的,所以考虑另一个方向的距离
#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 510;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN];
int ex_girl[MAXN];
int ex_boy[MAXN];
bool vis_girl[MAXN];
bool vis_boy[MAXN];
int match[MAXN];
int slack[MAXN];
int N,M;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < M; ++boy) {
if (vis_boy[boy]) continue;
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) {
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) {
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap);
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match);
memset(ex_boy, 0, sizeof ex_boy);
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < M; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
for (int i = 0; i < N; ++i) {
fill(slack, slack + M, INF);
while (1) {
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break;
int d = INF;
for (int j = 0; j < M; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
if (vis_girl[j]) ex_girl[j] -= d;
}
for(int j=0;j<M;j++)
{
if(vis_boy[j]) ex_boy[j]+=d;
else slack[j]-=d;
}
}
}
int res = 0;
for (int i = 0; i < M; ++i)
{
if(match[i]==-1||love[match[i]][i]==-INF) continue;
res += love[ match[i] ][i];
}
return res;
}
int main()
{
while(scanf("%d",&N)!=EOF)
{
if(N==0) break;
int val[MAXN];
for(int i=0;i<N;i++)
{
scanf("%d",&val[i]);
}
int index[MAXN];
int box=0;
for(int i=0;i<N;i++)
{
if(!val[i]) index[box++]=i;
}
int cnt=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
love[i][j]=-INF;
}
}
for(int i=0;i<N;i++)
{
if(val[i]>1)
{
for(int j=1;j<val[i];j++)
{
for(int k=0;k<box;k++)
{
love[cnt][k]=-min(abs(index[k]-i),N-abs(index[k]-i));
}
cnt++;
}
}
}
N=cnt;
M=box;
printf("%d\n",-KM());
}
return 0;
}
F - One fihgt one
题意;
吕布和曹操对战，给出两队的对战情况，要求吕布伤害最小，即求最小权匹配
题解:
这里用到了map<string,int>,第一次知道插入map的key不单单是用string,还可以是char数组
#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
const int MAXN = 205;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN];
int ex_girl[MAXN];
int ex_boy[MAXN];
bool vis_girl[MAXN];
bool vis_boy[MAXN];
int match[MAXN];
int slack[MAXN];
int N,M;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < M; ++boy) {
if (vis_boy[boy]) continue;
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) {
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) {
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap);
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match);
memset(ex_boy, 0, sizeof ex_boy);
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < M; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
for (int i = 0; i < N; ++i) {
fill(slack, slack + M, INF);
while (1) {
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break;
int d = INF;
for (int j = 0; j < M; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
if (vis_girl[j]) ex_girl[j] -= d;
}
for(int j=0;j<M;j++)
{
if(vis_boy[j]) ex_boy[j]+=d;
else slack[j]-=d;
}
}
}
int res = 0;
for (int i = 0; i < M; ++i)
{
if(match[i]==-1||love[match[i]][i]==-INF) continue;
res += love[ match[i] ][i];
}
return res;
}
int main()
{
int T;
int hurt;
int index1,index2;
char name1[25];
char name2[25];
int x,y;
while(scanf("%d%d%d",&N,&M,&T)!=EOF)
{
map<string,int> lv,cao;
index1=0;
index2=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
love[i][j]=-INF;
}
}
while(T--)
{
scanf("%s%s%d",name1,name2,&hurt);
map<string,int>::iterator it;
it=lv.find(name1);
if(it==lv.end())
{
x=index1;
lv[name1]=index1++;
}
else x=it->second;
it=cao.find(name2);
if(it==cao.end())
{
y=index2;
cao[name2]=index2++;
}
else y=it->second;
love[x][y]=-hurt;
}
printf("%d\n",-KM());
}
return 0;
}
P - Going Home
题意:
这题和B题一样的,代码就不贴了
Q - Supervisor, Supervisee
题意:
n个雇员和n个雇主,给出n个雇员对每个雇主的评价(越低分越满意),同样给出n个雇主对每个雇员的评价(越低分越满),求出匹配方案使得总满意度最高(分数最低)。如果存在多种方案,输出所有的方案。
题解: ( 双匹配边 + 输出所有合理方案 )
这题出现了双边,即匹配的双方都有各自的看法,但是其实还是一样的,只要建图两次,两次的满意度加在一起就可以了,然后求最小权匹配。
至于输出多种方案:因为0 < N < 15,N比较小,我们先求出最小权匹配的ans,然后再对雇员进行全排列,每个雇主与之匹配,检测匹配值是否等于ans,等于再输出相应的方案。注意:dfs进行全排列的时候,需要剪枝:如果当前积分比ans还要小(我套的是边取负值,最大权匹配的模板),那就不要继续走下去了,最后的方案一定不是对于ans的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
int visb[MAXN],visg[MAXN];
int eboy[MAXN],egirl[MAXN];
int match[MAXN],slack[MAXN];
int love[MAXN][MAXN],n,res;
bool DFS(int girl)
{
visg[girl]=1;
for(int i=1;i<=n;i++)
{
if(visb[i]) continue;
int gap=eboy[i]+egirl[girl]-love[girl][i];
if(gap==0)
{
visb[i]=1;
if(match[i]==-1||DFS(match[i]))
{
match[i]=girl;
return true;
}
}
else slack[i]=min(slack[i],gap);
}
return false;
}
void km()
{
memset(eboy,0,sizeof(eboy));
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++)
{
egirl[i]=love[i][1];
for(int j=2;j<=n;j++)
{
egirl[i]=max(egirl[i],love[i][j]);
}
}
for(int i=1;i<=n;i++)
{
memset(slack,INF,sizeof(slack));
while(true)
{
memset(visb,0,sizeof(visb));
memset(visg,0,sizeof(visg));
if(DFS(i)) break;
int d=INF;
for(int j=1;j<=n;j++)
{
if(!visb[j]) d=min(d,slack[j]);
}
for(int j=1;j<=n;j++)
{
if(visg[j]) egirl[j]-=d;
if(visb[j]) eboy[j]+=d;
else slack[j]-=d;
}
}
}
res=0;
for(int i=1;i<=n;i++)
{
res+=love[match[i]][i];
}
}
int num[MAXN],vis[MAXN],cnt,sum;
void km_dfs(int dept)//全排列
{
if(sum<res) return;//剪枝
if(dept>n)
{
if(sum!=res) return;
printf("Best Pairing %d\n",++cnt);
for(int i=1;i<=n;i++)
{
printf("Supervisor %d with Employee %d\n",i,num[i]);
}
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
vis[i]=1;
num[dept]=i;
sum+=love[dept][i];
km_dfs(dept+1);
vis[i]=0;//回溯
sum-=love[dept][i];//回溯
}
}
int main()
{
int t,x;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
scanf("%d",&n);
memset(love,0,sizeof(love));
for(int i=1;i<=n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&x);
love[x][i]-=j;
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&x);
love[i][x]-=j;
}
}
km();
cnt=sum=0;
memset(vis,0,sizeof(vis));
//平均满意度:因为有2*n个点,所以除以2*n
printf("Data Set %d, Best average difference: %.6lf\n",cas,0.5*(-res)/n);
km_dfs(1);
printf("\n");
}
}
