F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2127 >> 求教:为何TLE
walker90 @ 2017-12-28 16:11:06
[ Quote ] [ Edit ] [ Delete ] 1#
orzorz大佬们可以帮我看看我的程序为何会TLE吗,感激不尽!!!!膜拜大佬们!!!
附代码:
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>

using namespace std;

#define MAXN 1010
#define inf (1<<29)
int n,m;
#define P(x,y) ((x-1)*m+(y))
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
w=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void print(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x>=10)
{
print(x/10);
}
putchar(x%10+'0');
}
struct edge
{
int to,nxxt,weight;
}e[MAXN<<2];
int head[MAXN];
int sum;
int tot;
int ans;
int q[MAXN];
int dep[MAXN];
int mark[MAXN][MAXN];
int cnt=-1;
int frontt,backk;
int S,T;
int x,y;
int vv;
int a[2][MAXN][MAXN];
inline void add(int s,int q,int c)
{
cnt++;
e[cnt].to=q;
e[cnt].weight=c;
e[cnt].nxxt=head[s];
head[s]=cnt;
}
inline void in(int from,int to,int val)
{
add(from,to,val);
add(to,from,0);
}
inline void sp_in(int from,int to,int val)
{
add(from,to,val);
add(to,from,val);
}
inline bool bfs()
{
frontt=1;backk=0;
memset(dep,-1,sizeof(dep));
q[++backk]=S;
dep[S]=0;
while(frontt<=backk)
{
int x=q[frontt++];
for(int i=head[x];i!=-1;i=e[i].nxxt)
{
int t=e[i].to,w=e[i].weight;
if(dep[t]==-1&&w>0)
{
dep[t]=dep[x]+1;
q[++backk]=t;
}
}
}
return dep[T]!=-1?1:0;
}
inline int dfs(int x,int v)
{
if(x==T||v==0)return v;
int maxx=0;
for(int i=head[x];i!=-1;i=e[i].nxxt)
{
int t=e[i].to,w=e[i].weight;
if(dep[t]==dep[x]+1&&w>0)
{
int f=dfs(t,min(v,w));
if(f)
{
e[i].weight-=f;
e[i^1].weight+=f;
maxx+=f;
v-=f;
if(v==0)break;
}
}
}
if(!maxx)dep[x]=-1;
return maxx;
}
inline void dinic()
{
ans=0;
while(bfs())
{
ans+=dfs(S,inf);
}
}
int main()
{
memset(head,-1,sizeof(head));
n=read();m=read();
S=0;T=n*m+3;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[0][i][j]=read();
sum+=a[0][i][j];
a[0][i][j]<<=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[1][i][j]=read();
sum+=a[1][i][j];
a[1][i][j]<<=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
mark[i][j]=++tot;
}
}
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=m;j++)
{
vv=read();
sum+=vv;
a[0][i][j]+=vv;
a[0][i+1][j]+=vv;
sp_in(mark[i][j],mark[i+1][j],vv);
}
}
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=m;j++)
{
vv=read();
sum+=vv;
a[1][i][j]+=vv;
a[1][i+1][j]+=vv;
sp_in(mark[i][j],mark[i+1][j],vv);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m-1;j++)
{
vv=read();
sum+=vv;
a[0][i][j]+=vv;
a[0][i][j+1]+=vv;
sp_in(mark[i][j],mark[i][j+1],vv);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m-1;j++)
{
vv=read();
sum+=vv;
a[1][i][j]+=vv;
a[1][i][j+1]+=vv;
sp_in(mark[i][j],mark[i][j+1],vv);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
in(S,mark[i][j],a[0][i][j]);
in(mark[i][j],T,a[1][i][j]);
}
}
dinic();
sum-=(ans>>1);
print(sum);
putchar(10);
}
[Top] [Previous Page] [Next Page]

HOME Back