原题地址
强烈吐槽百度使我的博客里第二次出现 http 链接。
题意概述
度度熊有一个可能是整数规划的问题:
给定 $n×n$ 个整数 $a_{i,j}(1 \leq i,j \leq n)$,要找出 $2n$ 个整数 $x_1,x_2,…,x_n,y_1,y_2,…,y_n$ 在满足 $x_i+y_j \leq a_{i,j}(1 \leq i,j \leq n)$ 的约束下最大化目标函数 $\sum_{i=1}^{n} x_i + \sum_{i=1}^{n} y_i$,
你需要帮他解决这个整数规划问题,并给出目标函数的最大值。
输入与输出
输入
第一行包含一个整数 $T$,表示有 $T$ 组测试数据。
接下来依次描述 $T$ 组测试数据。对于每组测试数据:
第一行包含一个整数 $n$,表示该整数规划问题的规模。
接下来 $n$ 行,每行包含 $n$ 个整数,其中第 $i$ 行第 $j$ 列的元素是 $a_i$,$j$。
保证 $1≤T≤20$,$1≤n≤200$,$-10^9 \leq a_{i,j} \leq 10^9(1 \leq i,j \leq n)$。
输出
对于每组测试数据,输出一行信息 “Case #x: y”(不含引号),其中 x 表示这是第 x 组测试数据,y 表示目标函数的最大值,行末不要有多余空格。
样例
输入
2
1
0
2
1 2
3 4
输出
Case #1: 0
Case #2: 5
思路
Sadly my Chinese IME is down and I can’t type my thought here.
代码
#include
#define maxn 420
#define ll long long
#define INF 0x777777777777777
using namespace std;
int a[maxn][maxn],head[maxn];
ll dis[maxn];
int vis[maxn],cnt,s,t,n;
struct Edge{
int to,next,val;
ll cost;
Edge(int a=0,int b=0,int c=0,ll d=0){
to=a,next=b,val=c,cost=d;
}
}l[maxn*maxn];
struct Pre{
int id,from;
Pre(int a=0,int b=0){
id=a,from=b;
}
}pre[maxn];
void Add(int a,int b,int c,ll d){
l[++cnt]=Edge(b,head[a],c,d);
head[a]=cnt;
}
bool Spfa(){
queueq;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q.push(s);
dis[s]=0;
while(!q.empty()){
int hq=q.front();q.pop();vis[hq]=0;
for (int i=head[hq];i;i=l[i].next){
int v=l[i].to;
if (dis[v]>dis[hq]+l[i].cost&&l[i].val){
dis[v]=dis[hq]+l[i].cost;
pre[v]=Pre(i,hq);
if (!vis[v]) q.push(v),vis[v]=1;
}
}
}
return dis[t]>n;
s=0,t=2*n+1;
for (int i=1;i<=n;i++){
Add(s,i,1,0);
Add(i,s,0,0);
Add(i+n,t,1,0);
Add(t,i+n,0,0);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
ll tem;
cin>>tem;
Add(i,j+n,1,tem);
Add(j+n,i,0,-tem);
}
cout<>T;
while(T--){
cout<<"Case #"<<++oj8k<<": ";
Reset();
Solve();
}
}