POJ 1459 , MLE, 求解答，郁闷
就是一个最大流的基本问题，怎么会是 Memory Limit Exceed,怎么调都找不出来，谢谢了，测试样例通过。
#include <iostream>POJ
#include <string>
#include <queue>
#include <cstring>
using namespace std;
const intmaxNum = 100;
intpoitMatrix[maxNum + 2][maxNum + 2];
intflowMatrix[maxNum + 2][maxNum + 2];
inth[maxNum + 2];
inte[maxNum + 2];
intmySum;
intn, np, nc, m;
queue<int>nodeQ;
struct nodeLink
{
intnum;
nodeLink*next;
};
nodeLink*nodes[maxNum + 2];
void initPreflow(int n)
{
h[0] = n + 2;
for(int i = 0; i != n + 2; ++i){
if(poitMatrix[0][i] > 0){
flowMatrix[0][i] = poitMatrix[0][i];
flowMatrix[i][0] = - poitMatrix[0][i];
e[i] = poitMatrix[0][i];
nodeQ.push(i);
e[0] -= poitMatrix[0][i];
}
}
}
void push(int u, int v)
{
int df = min(e[u], poitMatrix[u][v] - flowMatrix[u][v]);
flowMatrix[u][v] += df;
flowMatrix[v][u] = -flowMatrix[u][v];
e[u] -= df;
e[v] += df;
if(v == n + 1){
mySum += df;
}
}
void relabel(int u)
{
++h[u];
}
void push_relabel()
{
int tmpn;
while(!nodeQ.empty()){
tmpn = nodeQ.front();
nodeQ.pop();
int flag = 0;
for(int i = 0; i != n + 2; ++i){
if(h[tmpn] == h[i] + 1 &&
poitMatrix[tmpn][i] > flowMatrix[tmpn][i]){
push(tmpn, i);
if(e[i] > 0 && i != n + 1){
nodeQ.push(i);
}
flag = 1;
}
}//end for
if(e[tmpn] > 0){
if(flag == 0){
relabel(tmpn);
}
nodeQ.push(tmpn);
}
//cout << tmpn << ' ' << mySum << endl;
//for(int i = 0; i != n + 2; ++i){
//cout << e[i] << ' ';
//}
//cout << endl << ' ';
//for(int i = 0; i != n + 2; ++i){
//cout << h[i] << ' ';
//}
//cout << endl << endl;
//cout << flowMatrix[4][8] << endl;
//system("pause");
}//end while
}
int main()
{
//memset(nodes, 0, sizeof(nodes));
while(cin >> n >> np >> nc >> m){
mySum = 0;
memset(poitMatrix, 0, sizeof(poitMatrix));
memset(flowMatrix, 0, sizeof(flowMatrix));
memset(e, 0, sizeof(e));
memset(h, 0, sizeof(h));
stringtmpstr;
inttmpn = 0;
intprePoint = 0;
intnxtPoint = 0;
intflow = 0;
while(m--){
cin >> tmpstr;
for(int i = 1; i != tmpstr.size(); ++i){
if(tmpstr[i] == ','){
prePoint = tmpn;
tmpn = 0;
}else if(tmpstr[i] == ')'){
nxtPoint = tmpn;
tmpn = 0;
}else{
tmpn = (tmpn * 10 + (tmpstr[i] - '0'));
}
}//end for
flow = tmpn;
tmpn = 0;
poitMatrix[prePoint + 1][nxtPoint + 1] = flow;
}//end while
while(np--){
cin >> tmpstr;
for(int i = 1; i != tmpstr.size(); ++i){
if(tmpstr[i] == ')'){
nxtPoint = tmpn;
tmpn = 0;
}else{
tmpn = tmpn * 10 + (tmpstr[i] - '0');
}
}
flow = tmpn;
tmpn = 0;
poitMatrix[0][nxtPoint + 1] = flow;
}//end while
while(nc--){
cin >> tmpstr;
for(int i = 1; i != tmpstr.size(); ++i){
if(tmpstr[i] == ')'){
prePoint = tmpn;
tmpn = 0;
}else{
tmpn = tmpn * 10 + (tmpstr[i] - '0');
}
}
flow = tmpn;
tmpn = 0;
poitMatrix[prePoint + 1][n + 1] = flow;
}//end while
initPreflow(n);
push_relabel();
cout << mySum << endl;
}
//system("pause");
return 0;
}
