返利网站建设服务,wordpress适配熊掌号,飞翔时代 网站建设,网站的图片怎么制作题干#xff1a;
众所周知#xff0c;在各种对抗类游戏里装备都是很重要的一环#xff0c;不同的出装方案会给玩家带来不同的强度。
dalao手里有N件装备#xff0c;现在dalao要把装备分给N个队友#xff0c;每个队友只能分一件装备#xff0c;而每个队友穿上不同的装…题干
众所周知在各种对抗类游戏里装备都是很重要的一环不同的出装方案会给玩家带来不同的强度。
dalao手里有N件装备现在dalao要把装备分给N个队友每个队友只能分一件装备而每个队友穿上不同的装备会有不同程度的强度提升。
现在给出每个队友对每件装备的强度提升的值请问dalao的所有分配方案里最多能让团队的总强度提升多少呢
输入描述: 第一行有一个整数T表示数据的组数不会超过150组
每组数据第一行包含一个整数N接下来会有N行每行有N个整数其中第 a 行的第 b 个数字表示第 a 个队友穿上第 b 件装备的强度提升。任何队员穿任何装备的强度提升都不会超过20000。 输出描述:
对于每组数据在一行内输出一个整数表示强度能够提升的最大值 示例1
输入
复制
2
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 3 5
2 4 6
7 9 11
输出
复制
34
16
解题报告 不难发现其实就是个二分最优匹配可以选择KM算法或者费用流来解决这个问题。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
using namespace std;const int MAXN 70000;
const int MAXM 100005;
const int INF 0x3f3f3f3f;
struct Edge {int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;
void init(int n) {N n;tol 0;memset(head, -1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost) {edge[tol].to v;edge[tol].cap cap;edge[tol].cost cost;edge[tol].flow 0;edge[tol].next head[u];head[u] tol;edge[tol].to u;edge[tol].cap 0;edge[tol].cost -cost;edge[tol].flow 0;edge[tol].next head[v];head[v] tol;
}
bool spfa(int s,int t) {queueintq;for(int i 0; i N; i) {dis[i] INF;vis[i] false;pre[i] -1;}dis[s] 0;vis[s] true;q.push(s);while(!q.empty()) {int u q.front();q.pop();vis[u] false;for(int i head[u]; i !-1; i edge[i].next) {int v edge[i].to;if(edge[i].cap edge[i].flow dis[v] dis[u] edge[i].cost ) {dis[v] dis[u] edge[i].cost;pre[v] i;if(!vis[v]) {vis[v] true;q.push(v);}}}}if(pre[t] -1)return false;else return true;
}
int minCostMaxflow(int s,int t,int cost) {int flow 0;cost 0;while(spfa(s,t)) {int Min INF;for(int i pre[t]; i !-1; i pre[edge[i^1].to]) {if(Min edge[i].cap-edge[i].flow)Min edge[i].cap-edge[i].flow;}for(int i pre[t]; i !-1; i pre[edge[i^1].to]) {edge[i].flow Min;edge[i^1].flow- Min;cost edge[i].cost * Min;}flow Min;}return flow;
}
int main()
{int n;int t;cint;while(t--) {scanf(%d,n);//int st0,edn1n21;int st 0,edn*21;init(ed1);int a,b,w;for(int i 1; in; i) {for(int j n1; j2*n; j) {scanf(%d,w);addedge(i,j,1,-w);}}for(int i 1; in; i) addedge(st,i,1,0);for(int i n1; i2*n; i) addedge(i,ed,1,0);int cost;int ans minCostMaxflow(st,ed,cost);printf(%d\n,-cost);}return 0 ;
}
