题目 https://www.luogu.org/problemnew/show/P1559
根据题目, 我们很快能看出来, 这是一个带权的二分图匹配问题.
二分图匹配, 我们可以跑最大流 https://www.luogu.org/problemnew/show/P3376
而带上权值呢? 就可以跑最小费用最大流 233.
啥? 不是求最大吗? 怎么可以跑最小费用?
其实是可以的. 对于最基础的最小费用最大流: 每次求一条可以增广的最短路. 然后增广.
而我们根据这个题, 我们需要求得是最大, 也就是最长路.
我们就可以, 将权值取负数, 然后用 SPFA 跑最短路.
这样问题就迎刃而解了.(dij 好像也可以, 只不过我太 vegetable, 不会
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #include<cstring>
- using namespace std;
- struct node
- {
- int point;
- int flow;
- int val;
- int nxt;
- };
- node line[100000];// 前项星
- int head[100],tail=-1;
- void add(int x,int y,int f,int v)
- {
- line[++tail].point=y;
- line[tail].flow=f;
- line[tail].val=v;
- line[tail].nxt=head[x];
- head[x]=tail;
- }// 加边
- int male[21][21];
- int famale[21][21];// 读入的数据, 看数组名就可以了, 不需要再解释了 233
- int max_cost;// 最大的费用, 就是答案
- int flow[100],last[100],dis[100];//last 是把每个点更新的边的编号
- int pre[100];
- bool inque[100];//SPFA 找最短的增广路所需要的数组
- bool SPFA(int begin,int end)
- {
- queue<int>q;
- memset(dis,10,sizeof(dis));
- memset(flow,0,sizeof(flow));
- memset(inque,0,sizeof(inque));
- memset(pre,0,sizeof(pre));// 初始化
- dis[begin]=0;pre[begin]=0;flow[begin]=0x7fffffff;// 源点流量无限
- inque[begin]=true;q.push(begin);
- while(!q.empty())
- {
- int pas=q.front(); q.pop();
- inque[pas]=false;
- for(int i=head[pas];i!=-1;i=line[i].nxt)// 遍历
- if(line[i].flow>0&&dis[line[i].point]>dis[pas]+line[i].val)// 一定要判断是否可以增广
- {
- dis[line[i].point]=dis[pas]+line[i].val;// 最短路
- last[line[i].point]=i;pre[line[i].point]=pas;// 储存边的编号, 以便后来更改
- flow[line[i].point]=min(flow[pas],line[i].flow);// 流量更新, 其实是不需要的, 因为我们现在在做二分图匹配嘛
- if(!inque[line[i].point])
- {
- inque[line[i].point]=true;
- q.push(line[i].point);
- }
- }
- }
- if(!pre[end]) return false;// 汇点是否到达
- return true;
- }
- void EK(int begin,int end)
- {
- while(SPFA(begin,end))
- {
- int pas=end;
- max_cost+=dis[end]*flow[end]*-1;// 因为我们取负存嘛, 所以要倒回来
- while(pas!=begin)// 从汇点到源点进行增广
- {
- line[last[pas]].flow-=flow[end];
- line[last[pas]^1].flow+=flow[end];//last 就用上了
- pas=pre[pas];
- }
- }
- return ;
- }
- int main()
- {
- int n;
- scanf("%d",&n);
- int len=n;
- for(int i=0;i<=(len<<1)+1;i++) head[i]=-1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- scanf("%d",&male[i][j]);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- scanf("%d",&famale[i][j]);// 初始化与输入
- for(int i=1;i<=n;i++)// 建图, 0 为源点, n*2+1 为汇点
- {
- add(0,i,1,0),add(i,0,0,0);
- add(len+i,(len<<1)+1,1,0),add((len<<1)+1,len+i,0,0);
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- add(i,len+j,1,male[i][j]*famale[j][i]*-1),add(len+j,i,0,male[i][j]*famale[j][i]);// 记住取负
- EK(0,(len<<1)+1);
- printf("%d",max_cost);
- }
[p1559] 运动员最佳匹配问题
来源: http://www.bubuko.com/infodetail-2647033.html