洛谷3973 TJOI2015线性代数（最小割+思维）

感觉要做出来这个题，需要一定的线代芝士

首先，我们来观察这个柿子。

我们将\(B\)的权值看作是收益的话，\(C\)的权值就是花费。

根据矩阵乘法的原理，只有当\(a[i]和a[j]\)都为\(1\)的时候，才能够获取到\(a[i][j]\)代价，而把\(a[i]\)弄成1，又会付出\(c[i]\)的代价。

那这不就是一个经典的最大全闭合子图模型吗？

我们令\(S \rightarrow (i,j)\)这个坐标对应的点。流量是\(b[i][j]\)，表示割去这个边，就舍弃了\(b[i][j]\)的收益

然后\(i\rightarrow t\)，流量是\(c[i]\)，表示如果这一位是1，要付出\(c[i]\)的代价。

然后\((i,j) \rightarrow i,(i,j)\rightarrow j\)

流量是\(inf\)

因为依赖关系没法取消

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk make_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 303003;

const int maxm = 2e6+1e2;

const int inf = 1e9;

int point[maxn],nxt[maxm],to[maxm],val[maxm];

int cnt=1,n,m;

int h[maxn];

int b[610][610];

int c[510];

void addedge(int x,int y,int w)

{

    nxt[++cnt]=point[x];

    to[cnt]=y;

    val[cnt]=w;

    point[x]=cnt;

}

void insert(int x,int y,int w)

{

    addedge(x,y,w);

    addedge(y,x,0);

}

int s,t;

queue<int> q;

bool bfs(int s)

{

    memset(h,-1,sizeof(h));

    h[s]=0;

    q.push(s);

    while (!q.empty())

    {

        int x = q.front();

        q.pop();

        for (int i=point[x];i;i=nxt[i])

        {

            int p = to[i];

            if (h[p]==-1 && val[i]>0)

            {

                h[p]=h[x]+1;

                q.push(p);

            }

        }

    }

    //cout<<1<<endl;

    if(h[t]==-1) return false;

    return true;

}

int dfs(int x,int low)

{

    if (x==t ||low==0) return low;

    int totflow=0;

    for (int i=point[x];i;i=nxt[i])

    {

        int p=to[i];

        if (val[i]>0 &&h[p]==h[x]+1)

        {

            int tmp = dfs(p,min(low,val[i]));

            val[i]-=tmp;

            val[i^1]+=tmp;

            low-=tmp;

            totflow+=tmp;

            if (low==0) return totflow;

        }

    }

    if (low>0) h[x]=-1;

    return totflow;

}

int dinic()

{

    int ans=0;

    while (bfs(s))

    {

        ans=ans+dfs(s,inf);

    }

    return ans;

}

int main()

{

  n=read();

  s=maxn-10;

  t=s+1;

  int sum=0;

  for (int i=1;i<=n;i++)

    for (int j=1;j<=n;j++)

    {

    	b[i][j]=read();

    	sum+=b[i][j];

    	insert(s,(i-1)*n+j,b[i][j]);

    }

  for (int i=1;i<=n;i++) c[i]=read(),insert(i+n*n,t,c[i]);

  for (int i=1;i<=n;i++)

    for (int j=1;j<=n;j++)

    {

    	insert((i-1)*n+j,i+n*n,inf);

    	insert((i-1)*n+j,j+n*n,inf);

    }

  sum-=dinic();

  cout<<sum;

  return 0;

}

巴特西

洛谷3973 TJOI2015线性代数（最小割+思维）

最新文章

热门文章