题意很明确,,就是一个二分图,求最优匹配,,蛋疼的是第二个要求,有多少个跟原来的匹配,就是优先选择原来的匹配,跟hdu 2853一样,将边的权值扩大1000倍,原来的匹配边+1,求得的值sum/1000就ok了,原来的匹配个数=sum%1000。。。。用费用流做效果不好,耗时太多
#include<stdio.h>
#include<queue>
#include<string.h>
const int N=110;
const int inf=0x3fffffff;
using namespace std;
int map[N][N],lx[N],ly[N],sx[N],sy[N],d[N],n,match[N],tch[N];
struct node
{
int w,hp,cut;
}P[100],R[100......
阅读全文