传送门：
Assignment
题意:题意直接那松神的题意了。给了你n个公司和m个任务，然后给你了每个公司处理每个任务的效率。然后他已经给你了每个公司的分配方案，让你求出最多能增大多少效率（即最大权值匹配减去原来的），然后问你至少要修改多少个关系（即修改多少条边）
思路：关键在于最小修改的老边，很巧妙的将老边和新边的权值做了修改，使得并且不改变km里面的顺序，可以说是很巧妙的了。之后就就直接跑km的板子就好了，挺好的题目，难在新旧边的处理。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdlib>
#include <vector>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+;
int nx,ny,k;
int g[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
map<pair<int,int>,int>mp;
bool dfs(int x)
{
visx[x] = true;
for(int y=;y<=ny;y++)
{
if(visy[y])
continue;
int tmp = lx[x] + ly[y] -g[x][y];
if(tmp == )
{
visy[y] = true;
if(linker[y] == - || dfs(linker[y]))
{
linker[y] = x;
return true;
}
}
else if(slack[y] > tmp)
slack[y] = tmp;
}
return false;
}
int KM()
{
memset(linker,-,sizeof linker);
memset(ly,,sizeof ly);
for(int i=;i<=nx;i++)
{
lx[i] = -INF;
for(int j=;j<=ny;j++)
{
if(g[i][j] > lx[i])
lx[i] = g[i][j];
}
}
for(int x = ;x <= nx ;x++)
{
for(int i=;i<=ny;i++)
slack[i] = INF;
while(true)
{
memset(visx,false,sizeof visx);
memset(visy,false,sizeof visy);
if(dfs(x))
break;
int d = INF;
for(int i = ;i <= ny;i ++ )
if(!visy[i] && d > slack[i])
d = slack[i];
for(int i = ;i <= nx; i++)
if(visx[i])
lx[i] -= d;
for(int i = ; i <= ny; i++)
{
if(visy[i])
ly[i] += d;
else
slack[i] -= d;
}
}
}
int res = ;
for(int i = ; i <= ny; i++)
if(linker[i] != -)
res += g[linker[i]][i];
return res;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
mp.clear();
memset(g,,sizeof g);
for(int i=;i<=n;i++) {
for (int j = ; j <= m; j++) {
int a;
scanf("%d", &a);
mp[make_pair(i, j)] = a;
g[i][j] = a * (n + );
}
}
int sum = ;
for(int i=;i<=n;i++)
{
int b;
scanf("%d",&b);
g[i][b] += ;
sum += mp[make_pair(i,b)];
}
nx = n;
ny = m;
int ans = KM();
printf("%d %d\n",n-ans%(n+),ans/(n+)-sum);
} }