【BZOJ 3996】 3996: [TJOI2015]线性代数（最小割）

3996: [TJOI2015]线性代数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1368 Solved: 832

Description

给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得

D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D

Input

第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.

接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。

Output

输出最大的D

Sample Input

3
1 2 1
3 1 0
1 2 3
2 3 7

Sample Output

2

HINT

1<=N<=500

Source

【分析】

　　化一下式子得到$D=\sum_{i=1}^{n}\sum_{j=1}^{n}A_i * A_j * B_{ij} - \sum_{i=1}^{n} A_i * C_i$

　　网络流建图。

　　S→Dot(i,j),流量为bij

　　Dot(i,j)→i 以及 Dot(i,j)→j,流量为 ∞

　　连边 i→T,流量为ci

　　设最小割为$x$,那么答案就是

　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　$\sum_{i=1}^{n}\sum_{j=1}^{n} B_{ij} - x$

　　经典模型？？不能弄成类似二分图那样的模型就只能这样了，虽然点很多，但是图比较简单应该还是很快吧？

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxn 510

 #define INF 0xfffffff

 int mymin(int x,int y) {return x<y?x:y;}

 struct node

 {

     int x,y,f,next,o;

 }t[Maxn*Maxn*];

 int first[Maxn*Maxn*],len;

 void ins(int x,int y,int f)

 {

     t[++len].x=x;t[len].y=y;t[len].f=f;

     t[len].next=first[x];first[x]=len;t[len].o=len+;

     t[++len].x=y;t[len].y=x;t[len].f=;

     t[len].next=first[y];first[y]=len;t[len].o=len-;

 }

 int ans;

 int dis[Maxn*Maxn*],st,ed;

 queue<int > q;

 bool bfs()

 {

     memset(dis,-,sizeof(dis));

     while(!q.empty()) q.pop();

     dis[st]=;q.push(st);

     while(!q.empty())

     {

         int x=q.front();

         for(int i=first[x];i;i=t[i].next) if(t[i].f>)

         {

             int y=t[i].y;

             if(dis[y]==-)

             {

                 dis[y]=dis[x]+;

                 q.push(y);

             }

         }

         q.pop();

     }

     if(dis[ed]==-) return ;

     return ;

 }

 int ffind(int x,int flow)

 {

     if(x==ed) return flow;

     int now=;

     for(int i=first[x];i;i=t[i].next) if(t[i].f>)

     {

         int y=t[i].y;

         if(dis[y]==dis[x]+)

         {

             int a=ffind(y,mymin(flow-now,t[i].f));

             t[i].f-=a;

             t[t[i].o].f+=a;

             now+=a;

         }

         if(now==flow) break;

     }

     if(now==) dis[x]=;

     return now;

 }

 void max_flow()

 {

     while(bfs())

     {

         ans-=ffind(st,INF);

     }

 }

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     int n;

     scanf("%d",&n);

     st=n*n+n+,ed=st+;

     len=;

     memset(first,,sizeof(first));

     ans=;

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

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

      {

          int x;

          scanf("%d",&x);

          ins(st,n*(i-)+j,x);

          ans+=x;

          ins(n*(i-)+j,n*n+i,INF);

          ins(n*(i-)+j,n*n+j,INF);

      }

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

     {

         int x;

         scanf("%d",&x);

         ins(n*n+i,ed,x);

     }

     max_flow();

     printf("%d\n",ans);

     return ;

 }

2017-03-24 08:40:32

巴特西

【BZOJ 3996】 3996: [TJOI2015]线性代数（最小割）

3996: [TJOI2015]线性代数

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

【BZOJ 3996】 3996: [TJOI2015]线性代数 （最小割）

3996: [TJOI2015]线性代数

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

【BZOJ 3996】 3996: [TJOI2015]线性代数（最小割）