本文主要是介绍POJ 1815 SAP+枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求字典序最小的割集的时候，我们不能用ek算法中，a[i]大于零则属于s， a[i]等于零则属于t来求。因为这样虽然能求出一种割集，但未必是最小的。本题用sap求出最大流之后，枚举所有的点，当删除改点的时候看最大流是否减小，减小则该点属于割集。
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
const int maxn = 500;struct Edge{int from, to, cap, flow;Edge(int _from, int _to, int _cap, int _flow):from(_from),to(_to),cap(_cap),flow(_flow){}
};
vector<Edge> es;
vector<int> g[maxn];
int s,t;
int n,mymap[210][210];
int p[maxn],d[maxn],gap[maxn],cur[maxn];
void addedge (int from, int to, int cap){es.push_back(Edge(from, to, cap, 0));es.push_back(Edge(to, from, 0,0));int num = es.size();g[from].push_back(num-2);g[to].push_back(num-1);
}
void BFS (){queue<int> q;memset(d, -1, sizeof(d));d[t] = 0;q.push(t);while(!q.empty()){int u = q.front();q.pop();for(int i = 0; i < g[u].size(); i++){Edge& e = es[g[u][i]];if(g[u][i]&1 && d[e.to]==-1){d[e.to] = d[u]+1;q.push(e.to);}}}
}
int augment (){int x = t;int a = int_max;while(x!=s){Edge& e = es[p[x]];a = (a < e.cap-e.flow ? a : e.cap-e.flow);x = es[p[x]].from;}x = t;while(x!=s){es[p[x]].flow += a;es[p[x]^1].flow -= a;x = es[p[x]].from;}return a;
}
int sap (){int flow = 0;BFS();memset(gap, 0, sizeof(gap));for(int i = 1; i <= 2*n; i++) if(d[i]!=-1) gap[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while(d[s] < 2*n-2){if(x==t){flow += augment();x = s;}int ok = 0;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow && d[x]==d[e.to]+1){ok = 1;p[e.to] = g[x][i];cur[x] = i;x = e.to;break;}}if(!ok){int mm = 2*n-2;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow) mm = (mm > d[e.to] ? d[e.to] : mm);}if(--gap[d[x]] == 0) break;gap[d[x]=mm+1]++;cur[x] = 0;if(x!=s) x = es[p[x]].from;}}return flow;
}int main(int argc, const char * argv[])
{while (scanf("%d %d %d", &n, &s, &t)!=EOF) {es.clear();for(int i = 0; i < maxn; i++) g[i].clear();memset(mymap, 0, sizeof(mymap));for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++) scanf("%d", &mymap[i][j]);}if(mymap[s][t]) {printf("NO ANSWER!\n"); continue;}for(int i = 1; i <= n; i++){if(i!=s && i!=t){addedge(i, n+i, 1);for(int j = 1; j <= n; j++){if(i!=j && mymap[i][j]){addedge(i+n, j, int_max);}}}else{for(int j = 1; j <= n; j++){if(i!=j && mymap[i][j]){addedge(i, j, int_max);}}}}int result = sap();vector<int> ans;if(result==0) cout << 0 << endl;else{int biaoji[maxn];int temp = result;memset(biaoji, 0, sizeof(biaoji));for(int u = 1; u <= n; u++){if(u==s || u==t) continue;es.clear();for(int i = 0; i < maxn; i++) g[i].clear();for(int i = 1; i <= n; i++){if(i==u || biaoji[i]) continue;if(i!=s && i!=t){addedge(i, n+i, 1);for(int j = 1; j <= n; j++){if(j==u || biaoji[j]) continue;if(i!=j && mymap[i][j]){addedge(i+n, j, int_max);}}}else{for(int j = 1; j <= n; j++){if(j==u || biaoji[j]) continue;if(i!=j && mymap[i][j]){addedge(i, j, int_max);}}}}int ttemp = sap();if(temp > ttemp) {biaoji[u] = 1; temp = ttemp; ans.push_back(u);}if(temp==0) break;}cout << result << endl;for(int i = 0; i < ans.size()-1; i++) printf("%d ", ans[i]);printf("%d\n", ans[ans.size()-1]);}}
}这篇关于POJ 1815 SAP+枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
