NC17384. Matrix Game
描述
输入描述
The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 20).
The next N lines describe Aij, each line contains M integers. (0 ≤ Aij ≤ 20).
输出描述
For each test case, print the case number and the answer.
示例1
输入:
2 2 3 4 8 5 2 4 6 3 3 1 5 2 3 5 4 2 3 4
输出:
Case 1: 7 Case 2: 7
说明:
for the first example, the number of balls after operations isC++14(g++5.4) 解法, 执行用时: 561ms, 内存消耗: 504K, 提交时间: 2018-08-05 17:52:28
#include<bits/stdc++.h>
using namespace std;
struct node
{
int to,cap,rev;
};
const int MAXN=0x3f3f3f3f;
vector<node>edge[1010];
queue<int>que;
int level[1010],iter[1010];
void add_edge(int u,int v,int f)
{
edge[u].push_back((node){v,f,(int)edge[v].size()});
edge[v].push_back((node){u,0,(int)edge[u].size()-1});
}
int dfs(int s,int t,int f)
{
if (s==t) return f;
for (int &i=iter[s];i<edge[s].size();i++)
{
node tmp=edge[s][i];
if (tmp.cap>0&&level[tmp.to]>level[s])
{
int d=dfs(tmp.to,t,min(f,tmp.cap));
if (d>0)
{
edge[s][i].cap-=d;
edge[tmp.to][tmp.rev].cap+=d;
return d;
}
}
}
return 0;
}
void bfs(int s)
{
level[s]=0;
que.push(s);
while (!que.empty())
{
s=que.front();
que.pop();
for (int i=0;i<edge[s].size();i++)
{
node tmp=edge[s][i];
if (level[tmp.to]==-1&&tmp.cap>0)
{
level[tmp.to]=level[s]+1;
que.push(tmp.to);
}
}
}
}
int max_flow(int s,int t)
{
int flow=0;
while (true)
{
memset(level,-1,sizeof(level));
memset(iter,0,sizeof(iter));
bfs(s);
if (level[t]==-1) break;
int f;
f=dfs(s,t,MAXN);
while (f>0)
{
flow+=f;
f=dfs(s,t,MAXN);
}
}
return flow;
}
void init(int s,int t)
{
for (int i=s;i<=t;i++) edge[i].clear();
}
int a[30][30];
int main()
{
int T;
scanf("%d",&T);
for (int kase=1;kase<=T;kase++)
{
int n,m;
scanf("%d%d",&n,&m);
int sum=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
sum+=a[i][j];
}
int ans=2e9;
int gcd=__gcd(n,m);
int lcm=n/gcd*m;
int lim=20*n*m;
int S=0,T=n+m+1;
for (int k=0;k<=lim;k+=lcm)
{
int cur1=k/n,cur2=k/m;
init(S,T);
for (int i=1;i<=n;i++) add_edge(S,i,cur1);
for (int i=1;i<=m;i++) add_edge(i+n,T,cur2);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
add_edge(i,j+n,a[i][j]);
int res=max_flow(S,T);
res=k-res+sum-res;
ans=min(ans,res);
}
printf("Case %d: %d\n",kase,ans);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 519ms, 内存消耗: 468K, 提交时间: 2018-08-12 13:20:37
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=50010;
#define ll long long
int read()
{
char c=getchar(); int x=0;
while(c>'9'||c<'0') c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
struct my
{
int y,next;
ll flow;
}e[maxn];
int len=1,linkk[maxn];
void ins(int x,int y,ll v)
{
e[++len].next=linkk[x],linkk[x]=len;
e[len].y=y,e[len].flow=v;
e[++len].next=linkk[y],linkk[y]=len;
e[len].y=x,e[len].flow=0;
}
int n,m;
int deep[maxn],q[maxn];
bool makelevel()
{
int head=0,tail=1;
memset(deep,0,10000);
deep[0]=1,deep[20000]=0;
while(head++<tail)
{
int tn=q[head];
for(int i=linkk[tn];i;i=e[i].next)
{
int to=e[i].y;
if(deep[to]||!e[i].flow) continue;
deep[to]=deep[tn]+1; q[++tail]=to;
}
}
return deep[20000];
}
int maxflow(int x,ll flow)
{
if(x==20000||!flow) return flow;
int maxx=0;
for(int i=linkk[x];i&&maxx<flow;i=e[i].next)
{
int to=e[i].y;
if(deep[to]!=deep[x]+1||!e[i].flow) continue;
int d=maxflow(to,min(flow-maxx,e[i].flow));
maxx+=d;
e[i].flow-=d; e[i^1].flow+=d;
}
return maxx;
}
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
ll a[210][210],col[210];
int main()
{
// freopen("in","r",stdin);
//freopen("out","w",stdout);
int t; cin>>t;
for(int g=1;g<=t;g++)
{
cin>>n>>m;
printf("Case %d: ",g);
int L=n/gcd(n,m)*m,ans=1e8,sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read(),sum+=a[i][j];
for(int k=0;k<=8000;k+=L)
{
len=1;
for(int i=0;i<=2000;i++) linkk[i]=0; linkk[20000]=0;
for(int i=1;i<=n;i++)
{
ins(0,i,k/n);
for(int j=1;j<=m;j++)
ins(i,j+1000,a[i][j]);
}
for(int i=1;i<=m;i++) ins(i+1000,20000,k/m);
int amo=0;
while(makelevel())
amo+=maxflow(0,1e8);
ans=min(ans,k-amo+sum-amo);
}
cout<<ans<<endl;
}
return 0;
}