【百度之星 2018 资格赛】整数规划 / 题解

原题地址

强烈吐槽百度使我的博客里第二次出现 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();
    }
}