Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## my code get a TLE,why?

Posted by andone at 2010-08-18 00:32:46 on Problem 2195
```#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 205;
const int inf = 9999999;
struct edge
{
int from,to,next,val,cost;
}e[maxn*maxn];
struct point
{
int x,y;
point(int a=0,int b=0)
{  x=a; y=b; }
}hp[maxn],mp[maxn];
void addedge(int from,int to,int f,int c)
{
}
bool spfa(int s,int t,int n)
{
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)  dist[i] = inf;
queue<int>que;
int p;
que.push(s);  pre[s]=s; dist[s] = 0; vis[s] = 1;
while(!que.empty())
{
p = que.front();  que.pop();   vis[p] = 0;
for(int q = head[p]; q != -1; q = e[q].next)
{

if(e[q].val > 0 && dist[e[q].to] > e[q].cost + dist[e[q].from])
{
dist[e[q].to] =  e[q].cost + dist[e[q].from];
pre[e[q].to] = e[q].from;
pos[e[q].to] = q;
if(!vis[e[q].to])
{
vis[e[q].to] = 1;
que.push(e[q].to);
}
}
}
}
return (pre[t] != -1 && dist[t] < inf);
}
int minCostFlow(int s,int t,int n)
{
int cost = 0;
while(spfa(s,t,n))
{
int f1 = inf;
for(int i = t; i != s; i = pre[i])
f1 = min(f1,e[pos[i]].val);
cost+=f1*dist[t];
for(int i = t; i != s; i = pre[i])
{
e[pos[i]].val -= f1;
e[pos[i]^1].val += f1;
}
}
return cost;
}
int main()
{
int n,m,xM[maxn],yM[maxn];
char ch[maxn];
while(scanf("%d%d",&m,&n)!=EOF && (m || n))
{
int n_hp=0, n_mp=0;
for(int i = 1;i <= m;i++)
{
scanf("%s",ch);
for(int j=0;j<n;j++)
{
if(ch[j] == 'H')
hp[++n_hp] = point(i,j+1);
else if(ch[j] == 'm')
mp[++n_mp] = point(i,j+1);
}
}
index = 0;
for(int i=1;i<=n_hp;i++)
{
for(int j=1;j<=n_mp;j++)
{
int l=abs(hp[i].x-mp[j].x)+abs(hp[i].y-mp[j].y);
}

}
for(int i=1;i<=n_hp;i++)
for(int i=1;i<=n_mp;i++)

printf("%d\n",minCostFlow(1+n_hp+n_mp,2+n_hp+n_mp,2+n_hp+n_mp));
}
return 0;
}
```

Followed by: