因为你用了三层for，没有优化，当然TLE咯
by nofall @ 2018-11-16 20:53:52
n<=9......
by huangzhewer @ 2018-11-16 20:54:34
你这就是暴力做法啊（一般有一点难度的题暴力都过不了）
by nofall @ 2018-11-16 20:54:41
```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define INF 0x7f7f7f7f
using namespace std;
struct Edge
{
int u;
int v;
int f;
int c;
int next;
}e[850];
int head[170];
int n,m,s,t;
int ecnt = 0;
inline void AddEdge(int _u,int _v,int _f,int _c)
{
e[ecnt].next = head[_u];
head[_u] = ecnt;
e[ecnt].u = _u;
e[ecnt].v = _v;
e[ecnt].f = _f;
e[ecnt].c = _c;
ecnt++;
}
inline void Add(int _u,int _v,int _f,int _c)
{
AddEdge(_u,_v,_f,_c);
AddEdge(_v,_u,0,-_c);
}
int dis[170];
bool inq[170];
int pre[170];
bool SPFA()
{
queue <int> q;
q.push(s);
memset(dis,0x7f,sizeof(dis));
memset(inq,0,sizeof(inq));
memset(pre,-1,sizeof(pre));
inq[s] = true;
dis[s] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
inq[cur] = false;
for (int i = head[cur];i != -1;i = e[i].next) {
if (e[i].f != 0 && dis[e[i].v] > dis[cur] + e[i].c) {
dis[e[i].v] = dis[cur] + e[i].c;
pre[e[i].v] = i;
if (!inq[e[i].v]) {
inq[e[i].v] = true;
q.push(e[i].v);
}
}
}
}
return dis[t] != INF;
}
void MICMAF(int &flow,int &cost)
{
flow = 0;
cost = 0;
while (SPFA()) {
int minF = INF;
for (int i=pre[t];i != -1;i=pre[e[i].u]) minF = min(minF,e[i].f);
flow += minF;
for (int i=pre[t];i != -1;i=pre[e[i].u])
{
e[i].f -= minF;
e[i^1].f += minF;
}
cost += dis[t] * minF;
}
}
int g[10][10];
inline int hashin(int x,int y)
{
return n*x+y+1;
}
inline int hashout(int x,int y)
{
return n*n + n * x + y + 1;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d",&n);
int x,y,v;
while (scanf("%d%d%d",&x,&y,&v) == 3)
{
if (x == 0 && y == 0 && v == 0) break;
x --;
y --;
g[x][y] = v;
}
s = 0;
t = 2 * n * n + 1;
Add(s,1,2,0);
Add(2*n*n,t,2,0);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
int in = hashin(i,j);
int out = hashout(i,j);
Add(in,out,1,0);
Add(in,out,1,-g[i][j]);
if (i != n - 1) Add(out,hashin(i+1,j),2,0);
if (j != n - 1) Add(out,hashin(i,j+1),2,0);
}
int f,c;
MICMAF(f,c);
printf("%d\n",-c);
return 0;
}
```
by nofall @ 2018-11-16 20:55:21
O(n^3)不可能过吧
by nofall @ 2018-11-16 20:56:18
...
by huangzhewer @ 2018-11-16 20:56:54
干嘛要这么多函数?
@[Lonely_people](/space/show?uid=118317)
by 大壶 @ 2018-11-16 20:57:02
@[大壶](/space/show?uid=117768)
无聊
by nofall @ 2018-11-16 20:57:49
4个for我过了
by 大壶 @ 2018-11-16 20:59:43
过了。。改了下读入，发现手残了
O(n^3)过的。动规。
评测记录在这[喏](https://www.luogu.org/recordnew/show/13854752)
by huangzhewer @ 2018-11-16 21:00:22