首页 » C++ » 【bzoj3996】[TJOI2015]线性代数

【bzoj3996】[TJOI2015]线性代数

原文 http://blog.csdn.net/wzf_2000/article/details/76698688

2017-08-05 11:20:07阅读(600)

首先转化题目:
给你nn个物品,可以选或不选。
选第ii个物品需要c[i]c[i]的代价。
同时选第ii和第jj个物品获得b[i][j]b[i][j]的收益
问最大收益。
网络流建图:
考虑sum=∑ni=1∑nj=1b[i][j]sum=\sum_{i=1}^{n}\sum_{j=1}^{n}b[i][j]
剩下就变成了算代价最小(也就是最小割)
建点(i,j)(i,j)和ii,对于每个点(i,j)(i,j),向i,ji,j连一条容量为infinf的边。
SS向每个点(i,j)(i,j)连一条容量为b[i][j]b[i][j]的边
每个点ii向TT连一条容量为c[i]c[i]的边。
然后跑最大流就好。

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 509
#define inf 0x3f3f3f3f
using namespace std;
int n,b[N][N],c[N],sum;
int number=1,pos,cur[N*N],dis[N*N];
bool vis[N*N];
vector<int> G[N*N];
struct edge
{
    int from,to,flow,cap;
    int rest()
    {
        return cap-flow;
    }
    void add(int x,int y,int z)
    {
        from=x,to=y,cap=z,flow=0;
    }
}e[N*N<<3];
void add(int x,int y,int z)
{
    e[++number].add(x,y,z);
    G[x].push_back(number);
    e[++number].add(y,x,0);
    G[y].push_back(number);
}
#define E e[G[x][i]]
bool bfs(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    dis[s]=0;
    vis[s]=1;
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for (int i=0;i<(int)G[x].size();i++)
            if (!vis[E.to]&&E.rest()>0)
            {
                vis[E.to]=1;
                dis[E.to]=dis[x]+1;
                Q.push(E.to);
            }
    }
    return vis[t];
}
int dfs(int x,int a,int t)
{
    if (x==t||a==0) return a;
    int flow=0,f;
    for (int &i=cur[x];i<(int)G[x].size();i++)
        if (dis[x]+1==dis[E.to]&&(f=dfs(E.to,min(a,E.rest()),t))>0)
        {
            E.flow+=f;
            e[G[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if (!a) break;
        }
    return flow;
}
int Maxflow(int s,int t)
{
    int flow=0;
    while (bfs(s,t))
    {
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,inf,t);
    }
    return flow;
}
#undef E
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            b[i][j]=read(),sum+=b[i][j];
            add(0,(i-1)*n+j,b[i][j]);
            add((i-1)*n+j,n*n+i,inf);
            add((i-1)*n+j,n*n+j,inf);
        }
    for (int i=1;i<=n;i++)
    {
        c[i]=read();
        add(n*n+i,n*n+n+1,c[i]);
    }
    printf("%d\n",sum-Maxflow(0,n*n+n+1));
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹