0_0_16385609_26495.cpp:2:5110: fatal error: GCC4.9.2/lib/gcc/x86_64-w64-mingw32/4.9.2/include/queue>usin: Invalid argument
#include<queue>using namespace std;class Graph{public: int cap[MaxVertex][MaxVertex]; //边容量矩阵,若无边，则为0 int flow[MaxVertex][MaxVertex]; //流矩阵 int V; //图结点个数 int maxflow; //最大流值 int MaxFlow(int ss, int tt); //求图中最大流，并返回流值protected://private: int s, t; //源点，汇点 int father[MaxVertex]; //记录增广路径和负环用 bool pfs(); void augment(int, int);};int Graph::MaxFlow(int ss, int tt){ s = ss, t = tt; memset(flow, 0, sizeof(flow)); maxflow = 0; while(pfs()) augment(s, t); return maxflow;}bool Graph::pfs(){ int v, j; queue<int> myque; memset(father, 0xff, sizeof(int)*V); while(!myque.empty()) myque.pop(); father[s] = s; myque.push(s); while(!myque.empty()) { v = myque.front(); myque.pop(); for(j = 0; j < V; ++j) if(cap[v][j]>0 && father[j]<0) { father[j] = v; if(j == t) return 1; myque.push(j); } } return 0;}void Graph::augment(int ss, int tt){ int tiny(INT_MAX); int v(tt), w(father[v]); do{ if(tiny > cap[w][v]) tiny = cap[w][v]; v = w, w = father[v]; }while(v != ss); v = tt, w = father[v]; do{ flow[w][v] += tiny; flow[v][w] -= tiny; cap[w][v] -= tiny; cap[v][w] += tiny; v = w, w = father[v]; }while(v != ss); maxflow += tiny;}class MincostGraph : public Graph{public: int cost[MaxVertex][MaxVertex]; //成本矩阵, 对称位置元素之和为0 int mincost; int MinCost();protected:struct EdgeNode{ int v, w; EdgeNode *next, *front; EdgeNode(int vv=0, int ww=0, EdgeNode *nn=NULL, EdgeNode *ff=NULL) : v(vv), w(ww), next(nn), front(ff) {}}; EdgeNode * lst; EdgeNode * p2edge[MaxVertex][MaxVertex]; int negcyc(); int findcyc(); void Augment(int, int); EdgeNode* Insert(EdgeNode *); void Delete(EdgeNode *); void Destroy();};void MincostGraph::Destroy(){ EdgeNode *p, *q; for(p = lst; p; p = q) { q = p->next; delete p; } lst = NULL;}int MincostGraph::MinCost(){ mincost = 0; int x, i, j; lst = NULL; for(i = 0; i < V; ++i) for(j = 0; j < V; ++j) if(cap[i][j] > 0) p2edge[i][j] = Insert(new EdgeNode(i, j)); else p2edge[i][j] = 0; while((x=negcyc())!=-1) Augment(x, x); for(i = 0; i < V; ++i) for(j = 0; j < V; ++j) if(flow[i][j]>0) mincost += flow[i][j]*cost[i][j]; Destroy(); return mincost;}MincostGraph:: EdgeNode* MincostGraph::Insert(EdgeNode * p){ if(lst) p->next = lst, lst->front = p; lst = p; return p;}void MincostGraph::Delete(EdgeNode *p){ if(!p) return; if(p == lst) { lst = p->next; lst->front = NULL; delete p; }else { p->front->next = p->next; p->next->front = p->front; delete p; }}void MincostGraph::Augment(int ss, int tt){ int tiny(INT_MAX); int v(tt), w(father[v]); do{ if(tiny > cap[w][v]) tiny = cap[w][v]; v = w, w = father[v]; }while(v != ss); v = tt, w = father[v]; do{ flow[w][v] += tiny; flow[v][w] -= tiny; cap[w][v] -= tiny; if(cap[w][v] == 0) { Delete(p2edge[w][v]); p2edge[w][v] = 0; } cap[v][w] += tiny; if(cap[v][w] == tiny) p2edge[v][w] = Insert(new EdgeNode(v, w)); v = w, w = father[v]; }while(v != ss); maxflow += tiny;}int MincostGraph::negcyc(){ int k, i, j; int D[MaxVertex] = {0}; bool flag; D[s] = 0; memset(father, 0xff, sizeof(int) * V); EdgeNode *itr; for(k = 0; k <= V; ++k) { flag = 0; for(itr = lst; itr; itr = itr->next) { i = itr->v, j = itr->w; if(D[j] > D[i]+cost[i][j]) { D[j] = D[i] + cost[i][j]; father[j] = i; flag = 1; if(k == V) return findcyc(); } } if(!flag) break; } return -1;}int MincostGraph::findcyc(){ int used[MaxVertex] = {0}; int i, j, k = 0; for(i = 0; i < V; ++i) { if(used[i]) continue; ++ k; for(j = i; j >= 0; j = father[j]) { if(used[j] == k) return j; used[j] = k; } }}int main(){ int i,j,n; while(scanf("%d",&n)!=EOF){ MincostGraph G; G.V = 2*n+2;////////////////////////////////////////////// for(i=0;i<G.V;++i) for(j=0;j<G.V;++j){ G.cap[i][j]=0; G.cost[i][j]=0; } for(i=1;i<=n;++i) G.cap[0][i]=1; for(i=n+1;i<=2*n;++i) G.cap[i][2*n+1]=1; for(i=1;i<=n;++i) for(j=n+1;j<=2*n;++j) G.cap[i][j]=1;////////////////////////////////////////////// for(i=1;i<=n;++i) for(j=n+1;j<=2*n;++j){ scanf("%d",&G.cost[i][j]); G.cost[j][i]=-G.cost[i][j]; } G.MaxFlow(0,2*n+1); int value=G.MinCost(); printf("%d\n",value); } return 0;}
|
