# 69 条题解

• @ 2017-07-08 22:05:01
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,e;
vector<int> f;
vector<int> a;
vector<int> e_x;
vector<int> e_y;
vector<int> e_v;
vector<int> pre;
vector<vector<int> > c;
deque<int> q;

int bfs_1(int s,int t)
{
f.resize(0);
f.resize(n+2,0);
f[s]=oo_max;
pre.resize(0);
pre.resize(n+2,-1);
pre[s]=s;
q.resize(0);
for (q.push_back(s);(!q.empty())&&pre[t]==-1;q.pop_front())
{
int now=q.front();
for (int i=1;i<=n+1;i++)
if (c[now][i]&&pre[i]==-1)
{
pre[i]=now;
f[i]=min(c[now][i],f[now]);
q.push_back(i);
}
}
return ((pre[t]!=-1)?f[t]:-1);
}

int max_flow_1(int s,int t)
{
int temp=0,ans=0;
while ((temp=bfs_1(s,t))!=-1)
{
for (int i=t;i!=s;i=pre[i])
c[pre[i]][i]-=temp,c[i][pre[i]]+=temp;
ans+=temp;
}
return ans;
}

int main()
{
while (~scanf("%d%d",&n,&e))
{
c.resize(0);
c.resize(n+2);
for (int i=1;i<=n+1;i++)
c[i].resize(n+2,0);
e_x.resize(0);
e_x.resize(e+1,0);
e_y.resize(0);
e_y.resize(e+1,0);
e_v.resize(0);
e_v.resize(e+1,0);
for (int i=1;i<=e;i++)
{
scanf("%d%d%d",&e_x[i],&e_y[i],&e_v[i]);
c[e_x[i]][e_y[i]]=c[e_y[i]][e_x[i]]=e_v[i];
}
scanf("%d",&m);
a.resize(0);
a.resize(m+1,0);
for (int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
c[a[i]][n+1]=oo_max;
}
printf("%d\n",max_flow_1(1,n+1));
}
}

• @ 2017-07-08 22:05:37

很H2O的题

• @ 2017-09-04 01:25:03

@sky1231:H2O不是氧气吗？？？

• @ 2017-04-26 21:54:43

简单最大流，dinic解决

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <ciso646>
#include <stack>
#include <cstdlib>
#include <vector>
#include <cstdint>
using namespace std;
const int maxn = 1000001;

struct edge
{
int v;
int w;
int next;
}g[500001];
queue<int> q;
int n, m, i, j, k, l, tot=-1, ans, total,t,s;

{
int ans = 0, f = 1;
char c = getchar();
while (!isdigit(c))
{
if (c == '-') f = -1;
c = getchar();
}
while (isdigit(c))
{
ans = ans * 10 + c - 48;
c = getchar();
}
return ans * f;
}

inline void addedge(int u, int v, int w)
{
++tot;
g[tot].v = v;
g[tot].w = w;
}

bool bfs()
{
while (!q.empty())
q.pop();
memset(dis, -1, sizeof(dis));
dis[s] = 0;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
for (i = head[u];i != -1;i = g[i].next)
{
int v = g[i].v;
if (dis[v] == -1 && g[i].w > 0)
{
dis[v] = dis[u] + 1;
q.push(v);
if (v == t) return true;
}
}
}
return false;
}

int dfs(int x,int flow)
{
if (x == t or (!flow))
return flow;
int w = 0;
for (int i = cur[x];i != -1 && w < flow; i = g[i].next)
{
int v = g[i].v;
if (dis[v] == dis[x] + 1 && g[i].w>0)
{
int delta = dfs(v, min(flow - w, g[i].w));
g[i].w -= delta;
g[i^1].w += delta;
w += delta;
if (g[i].w)
cur[x] = i;
}
}
if (w < flow)
dis[x] = -1;
return w;
}

int main()
{
s = 1;
t = n + 1;

for (int i = 1;i <= m;i++)
{
int u, v, w;
}
for (i = 1;i <= e;i++)
{
int k;
}
while (bfs())
{
for (i = 0;i <= t;i++)
int tans = dfs(s, maxn);
ans += tans;
}
printf("%d\n", ans);
system("pause");
return 0;

}

• @ 2016-05-28 23:16:06

感谢前辈！
70的要注意！无向图最大流
附上dinic算法代码：
c++
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
const int Max=2147383647;
int map[350][350];
int n,m,c,tas,ans;
int dis[350];
int Bfs(){
memset(dis,-1,sizeof(dis));
int l=1,r=2,que[4000];
dis[1]=0;
que[1]=1;
while(l<r){
int p=que[l];
for(int i=1;i<=n+1;i++)
if(dis[i]<0&&map[p][i]>0){
dis[i]=dis[p]+1;
que[r]=i;
r++;
}
l++;
}
if(dis[n+1]>0) return 1;
return 0;

}
int find(int deep,int minflow){
int mf=0;
if(deep==n+1) return minflow;
for(int i=1;i<=n+1;i++)
if( dis[i]==dis[deep]+1
&& map[deep][i]>0
&&(mf=find(i,min(map[deep][i],minflow)))){
map[deep][i]-=mf;
map[i][deep]+=mf;
return mf;
}
return 0;
}
int main(){

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int j,k,s;
scanf("%d%d%d",&j,&k,&s);
map[j][k]=s;
map[k][j]=s; 添加了这一句就变成无向图，不过我又有个困惑：这会影响增广吗？
}
scanf("%d",&c);
for(int i=1;i<=c;i++){
int j;
scanf("%d",&j);
map[j][n+1]=Max;
}
while(Bfs()){
while(tas=find(1,Max)){
// printf("%d ",tas);
ans+=tas;
}
}

printf("%d\n",ans);
return 0;
}


• @ 2016-12-26 23:11:12

测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 580 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 604 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 604 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 608 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 604 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 604 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 644 KiB, score = 10
Accepted, time = 30 ms, mem = 644 KiB, score = 100

最大流 = 最小割定理

代码
c++
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
using namespace std;
const int maxn = 520;
const int INF = 0x3f3f3f;
#define For(a,b) for(int i = (a);i<(b);i+=1)
#define Fore(a,b) for(int i = (a),i<=(b);i+=1)

struct Dinic{
struct Edge {
int from, to, cap, flow;
Edge(int a, int b, int c, int d) :from(a), to(b), cap(c), flow(d) {}
Edge(){}
friend bool operator < (const Edge& a, const Edge& b) {
return a.from < b.from || (a.from == b.from && a.to < b.to);
}
};

int n, m, s, t;
vector<Edge> old;
vector<Edge> edges;//边数两倍
vector<int> G[maxn];
bool vis[maxn]; // BFS使用
int d[maxn];
int cur[maxn];

void init(int n){ For(0, n) G[i].clear(); edges.clear(); }

void AddEdge(int from, int to, int cap, int flow){
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}

bool BFS(){ //构建层次网络，如果构建的时候汇点没有访问过证明已经不在网络中
Mem(vis, 0);
queue<int> Q;
Q.push(s);
vis[s] = 1;
d[s] = 0;
while (!Q.empty()){
int x = Q.front(); Q.pop();
For(0, G[x].size()){
Edge & e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow){
vis[e.to] = 1;
d[e.to] = d[x] + 1;//层次
Q.push(e.to);
}
}
}
return vis[t];
}

int DFS(int x, int a){
if (x == t || a == 0) return a;//如果已经到汇点或者增量是0，没必要继续因为已经找到了最大流
int flow = 0, f;
for (int & i = cur[x]; i<G[x].size(); i += 1){
Edge& e = edges[G[x][i]];
//如果e.to是x的儿子结点并且其增量大于0
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) break;
}
}
return flow;
}

int MaxFlow(int s, int t){
this->s = s; this->t = t;
int flow = 0;
while (BFS()){
Mem(cur, 0);
flow += DFS(s, INF);
}
return flow;
}
};

int main(){
Dinic D;
int n, e;
scanf("%d %d", &n, &e);
D.init(n + 2);
int a, b, c;
For(0, e){
scanf("%d %d %d", &a, &b, &c);
}
int m, aa;
scanf("%d", &m);
For(0, m){
scanf("%d", &aa);
}
printf("%d\n", D.MaxFlow(1, n + 1));

return 0;
}


• @ 2016-11-10 15:06:02

这题在点 1~N 之间的边是双向的，不是双向的会有三个点过不了
c++

#include <iostream>
#include <fstream>

#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 505;
const int INF = 0x7fffffff;

struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct EdmondsKarp {
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int a[maxn];
int p[maxn];

void init(int n) {
for (int i = 0; i < n; ++i) G[i].clear();
edges.clear();
}

void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0)); // reverse edge
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}

int Maxflow(int s, int t) {
int flow = 0;
for (;;) {
memset(a, 0, sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); ++i) {
Edge &e = edges[G[x][i]];
if (!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i];
a[e.to] = min(a[x], e.cap - e.flow);
Q.push(e.to);
}
}
if (a[t]) break;
}
if (!a[t]) break;
for (int u = t; u != s; u = edges[p[u]].from) {
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
};

int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif

EdmondsKarp ek;
int n, e; cin >> n >> e;
ek.init(n+2);
int a, b, w;
for (int i = 0; i < e; ++i) {
cin >> a >> b >> w;
}
int m; cin >> m;
for (int i = 0; i < m; ++i) {
cin >> a;
}
cout << ek.Maxflow(1, n+1) << endl;
return 0;
}

• @ 2016-10-04 09:41:03

• @ 2016-10-04 09:40:02

用EK实现~

c++ #include<iostream> #include<cstdio> #include<queue> using namespace std; int G[105][105]; int n=0,m=0,ans=0,maa=0; bool findr() { int l[100000],r=0,f=1,p[202]={0};//p[i] is father of i l[r]=1;bool bj=true,bj2=false;; while(1) { if(r==f) { bj=true; break; } for(int i=1;i<=m;i++) { if(G[l[r]][i]>0&&p[i]==0) { l[f]=i; f++; p[i]=l[r]; bj=false; if(i==m) bj2=true; } } if(bj2) { bj=false; break; } r++; } int minn=10000000,ii=m; if(!bj) { while(ii!=1) { if(G[p[ii]][ii]<minn) minn=G[p[ii]][ii]; ii=p[ii]; } ii=m; while(ii!=1) { G[p[ii]][ii]-=minn; G[ii][p[ii]]+=minn; ii=p[ii]; } ans+=minn; return true; } else return false; } int main() { scanf("%d%d",&m,&n); int v,vv,nn; for(int i=1;i<=n;i++) { scanf("%d%d%d",&v,&vv,&nn); G[v][vv]+=nn; G[vv][v]+=nn; } m++; scanf("%d",&maa);int hhd=0; for(int gga=0;gga<maa;gga++) { scanf("%d",&hhd); G[hhd][m]=2147482647; } while(findr()){} printf("%d",ans); return 0; } 

• @ 2016-06-21 20:59:33

最大流最小割，注意无向双边。
Dinic实现还是嫌长……
c++
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int INF = 2147483647;
const int maxn = 500;

struct Ed
{
int from,to,cap,flow;
Ed(int a=0,int b=0,int c=0,int d=0) : from(a),to(b),cap(c),flow(d) {}
};

int n,m,e,cur[maxn],d[maxn];
vector<int> G[maxn];
vector<Ed> edges;

inline void add_edges(int from,int to,int cap)
{
edges.push_back(Ed(from,to,cap,0));
edges.push_back(Ed(to,from,0,0));
int t=edges.size();
G[from].push_back(t-2);
G[to].push_back(t-1);
}

bool bfs(int s,int t)
{
memset(d,-1,sizeof(d));
queue<int> q;
d[s]=0;
q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=0;i<(int)G[now].size();i++)
{
Ed &e=edges[G[now][i]];
if(e.cap>e.flow&&d[e.to]==-1)
{
d[e.to]=d[now]+1;
q.push(e.to);
}
}
}
return d[t]>=0;
}

int dfs(int now,int a)
{
if(now==n+1||a==0) return a;
int flow=0,f;
for(int &i=cur[now];i<(int)G[now].size();i++)
{
Ed &e=edges[G[now][i]];
if(e.cap>e.flow&&d[e.to]==d[now]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edges[G[now][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}

int Dinic()
{
int max_flow=0,s=1,t=n+1;
while(bfs(s,t))
{
memset(cur,0,sizeof(cur));
max_flow+=dfs(s,INF);
}
return max_flow;
}

int main()
{
/*freopen("input","r",stdin);*/
scanf("%d%d",&n,&e);
for(int i=1;i<=e;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int k;
scanf("%d",&k);
}

int ans=Dinic();
printf("%d\n",ans);
return 0;
}

/* Accepted, time = 30 ms, mem = 648 KiB, score = 100 2016年6月21日星期二 */


• @ 2016-05-17 17:37:58

试着直接实现了一遍《算法导论》上的GENERIC-PUSH-RELABEL算法，代码好长。。。
c++
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int inf = 0x7fffffff;
const int maxn = 110;
const int maxe = 310;
int n, e, m;
int s, t;
int maxf;
int next[maxn];
int front[maxn];
int h[maxn];
int w[maxn];

struct edge {
int from;
int to;
int f;
int c;
edge (int from, int to, int f, int c) : from(from), to(to), f(f), c(c) {}
};

vector<edge> edges;
vector<int> g[maxn];

void add (int u, int v, int w) {
int m = edges.size();
edges.push_back (edge (u, v, 0, w));
g[u].push_back (m);
}

void init (int s) {
h[s] = t;
for (int i = 0; i < g[s].size(); i++) {
edge &p = edges[g[s][i]];
w[p.to] = p.f = p.c;
w[s] -= p.c;
}
}

void push (int u, int cur) {
edge &p = edges[g[u][cur]];
edge &q = edges[g[u][cur] + 1];
int temp = min (w[u], p.c - p.f);
if (p.c) p.f += temp;
else q.f -= temp;
w[u] -= temp;
w[p.to] += temp;
}

void relable (int u) {
int res = inf;
for (int i = 0; i < g[u].size(); i++) {
res = min(res, h[edges[g[u][i]].to]);
}
h[u] = res + 1;
}

void discharge (int u) {
int cur = 0;
while (w[u] > 0) {
if (cur == g[u].size()) {
relable (u);
cur = 0;
}
else if (edges[g[u][cur]].c > edges[g[u][cur]].f && h[u] == h[edges[g[u][cur]].to] + 1) push (u, cur);
else cur++;
}
}

void rtf (int s, int t) {
for (int i = 2; i < t; i++) {
next[i] = i + 1;
front[i] = i - 1;
}
front[2] = 0;
next[t - 1] = 0;
int u = next[2];
while (u) {
int old_height = h[u];
discharge (u);
if (h[u] > old_height) {
next[front[u]] = next[u];
front[next[u]] = front[u];
front[u] = 0;
}
u = next[u];
}
}

int main ()
{
//freopen ("in.txt", "r", stdin);
cin >> n >> e;
int temu, temv, temw;
for (int i = 0; i < e; i++) {
cin >> temu >> temv >> temw;
}
s = 1;
t = n + 1;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> temu;
}
init (s);
rtf (s, t);
for (int i = 0; i < g[s].size(); i++) {
maxf += edges[g[s][i]].f;
}
cout << maxf;
return 0;
}
`

• @ 2016-03-10 18:12:57

令人振奋，第一道网络流就一遍AC了！
虽然我存边的方式很丑，用了邻接矩阵，还存了每个点有多少出边。。。毕竟不想写前向星，看到数据范围就懒了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#define INF 2147383647
//dinic
//BFS FIRST AND TAG
//THEN DFS EVERYTIME UNTIL NOT FIND NEW PATH
//THEN BFS AGAIN UNTIL NOT REACH THE END
using namespace std;
int n,m,e;
int map[105][105];
int edge[105][105];
int tag[105];
int q[200];
int ans=0;
bool book[105];
bool bfs() {
memset(tag,0,sizeof(tag));
q[1]=1;
tag[1]=1;
return 1;
if (tag[v]==0 && map[u][v]>0) {
q[tail++]=v;
tag[v]=tag[u]+1;
}
}
}
return 0;
}
int dfs(int x,int flow) {
if (x==0) {
return flow;
}
for (int i=1,y;i<=edge[x][0];i++) {
y=edge[x][i];
if (!book[y] && tag[y]>tag[x] && map[x][y]>0) {
book[y]=1;
int res=dfs(y,min(flow,map[x][y]));
if (res>0) {
map[x][y]-=res;
map[y][x]+=res;
return res;
}
}
}
return 0;
}
int main() {
scanf("%d%d",&n,&e);
for (int i=1,a,b,w;i<=e;i++) {
scanf("%d%d%d",&a,&b,&w);
edge[a][++edge[a][0]]=b;
edge[b][++edge[b][0]]=a;
map[a][b]=map[b][a]=w;
}
scanf("%d",&m);
for (int i=1,tp;i<=m;i++) {
scanf("%d",&tp);
edge[tp][++edge[tp][0]]=0;
map[tp][0]=INF;
}
while (bfs()) {
while (1) {
memset(book,0,sizeof(book));
int res=dfs(1,INF);
if (res==0) break;
ans+=res;
}
}
printf("%d",ans);
return 0;

}

• @ 2016-02-02 14:49:28

一百题纪念！！！（模板网络流）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 20000+100
#define INF 1<<29
using namespace std;
int nn;
int h[N];
int n,m,w;
int s,t;
int temp,ans;
int p[N],q[N];
struct node
{
int b,next,w;
}e[N];
{
nn++;
e[nn].b=y;
e[nn].w=z;
e[nn].next=p[x];
p[x]=nn;
}
bool BFS()
{
for(int i=s;i<=t;i++)h[i]=0;
int l=0,r=0;
q[r++]=1;
h[s]=1;
while(l<r)
{
int k=q[l++];
if(k==n)return true;
for(int i=p[k];i;i=e[i].next)
{
int v=e[i].b;
if(!h[v]&&e[i].w>0)
{
q[r++]=v;
h[v]=h[k]+1;
}
}
}
return false;
}
int dinic(int pos,int max_flow)
{
if(pos==n)return max_flow;
int ans=0;
for(int i=p[pos];i;i=e[i].next)
{
int k=e[i].b,v=e[i].w;
if(v>0&&h[k]==h[pos]+1)
{
int minv=min(v,max_flow-ans);
v=dinic(k,minv);
e[i].w-=v;
e[i^1].w+=v;
ans+=v;
if(ans==max_flow)return ans;
}

}
return ans;
}
int solve()
{
int sum=0;
while(BFS())
{
sum+=dinic(s,INF);
}
return sum;
}
int main()
{
//freopen("D:\in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
s=1;
t=n;
scanf("%d",&w);
for(int i=1;i<=w;i++)
{
int tx;
scanf("%d",&tx);
}
printf("%d",solve());
return 0;
}

• @ 2016-02-01 16:42:43

大神说最大流过了，算法就入门了 好激动。。。楼下说的很不错，提供一个dfs找增广路代码
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int n, e;
int End;
#define INF 100000000
// end = n+1

struct edge {
int from, to, dis;
int next;
} edges[1000];
int pos = 0;
bool markedVisiting[1000];
stack<int> edgeSub;

void push(int from, int to, int dis)
{
edges[++pos].from = from;
edges[pos].to = to;
edges[pos].dis = dis;
}
////////////////////////////////////

int dfsFindPath(int from) {
if (markedUnlink[from] || markedVisiting[from]) return 0;
// not linked or is visiting
if (from == End) return INF;
markedVisiting[from] = true;
for (int v = head[from]; v; v = edges[v].next) {
int length = min(edges[v].dis, dfsFindPath(edges[v].to));
if (length > 0) {
edgeSub.push(v);
markedVisiting[from] = false;
return length;
}
}
return 0;
}

int maxFlow()
{
int anslength = 0;
while (1) {
while (!edgeSub.empty()) {
edgeSub.pop();
}
return anslength;
}
}

int main()
{
memset (markedVisiting,0,sizeof(markedVisiting));
int w;
cin >> n >> e;
End = n+1;
for (int i = 1; i <= e; i ++) {
int a, b, l;
cin >> a >> b >> l;
push(a,b,l);
push(b,a,l);
}
cin >> w;
for (int i = 1; i <= w; i++) {
int t;
cin >> t;
push(t,n+1,INF);
}
cout << maxFlow() << endl;
return 0;
}

• @ 2015-10-30 11:15:33

裸最小割 根据最小割最大流定理 就是求最大流，建立一个超级汇点n+1 把所有的传送点加一条到n+1，容量为无限大的边，然后求1到n+1的最大流
用的lrj书上的的dinic算法

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct edge{
int cap,flow,from,to;
edge(){}
edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){}
};
const int N=10010,INF=2099999999;
vector<edge> edges;
vector<int> g[N];
int d[N],vis[N],cur[N],s,t,n,e,a,b,w,m,ans;

edges.push_back(edge(from,to,cap,0));
edges.push_back(edge(to,from,cap,cap));
int m=edges.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
}

bool bfs(){
queue<int> q;
memset(vis,0,sizeof(vis));
vis[s]=true;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<g[x].size();i++){
if(!vis[edges[g[x][i]].to] && edges[g[x][i]].cap>edges[g[x][i]].flow )
d[edges[g[x][i]].to]=d[x]+1,vis[edges[g[x][i]].to]=true,q.push(edges[g[x][i]].to);
}
}
return vis[t];
}
int dfs(int x,int a){//a表示从开始到现在的最小残量
if(x==t||a==0) return a;
int flow=0,f;
for(int& i=cur[x];i<g[x].size();i++){
edge& e=edges[g[x][i]];
if( d[x]+1==d[e.to] && (f=dfs(e.to,min(a,e.cap-e.flow)))>0){
e.flow+=f;edges[g[x][i]^1].flow-=f;//处理这条边和反向边
flow+=f;a-=f;//处理之前的边
if(a==0) break;
}
}
return flow;
}
int maxflow(){
int flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}

int main(){
freopen("1524.in","r",stdin);freopen("1524.out","w",stdout);
scanf("%d%d",&n,&e);
scanf("%d",&m);
s=1,t=n+1;
ans=maxflow();
printf("%d",ans);
return 0;
}

• @ 2013-05-11 14:04:52

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 276 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 276 KiB, score = 10
Accepted, time = 0 ms, mem = 276 KiB, score = 100

终于0S了。。。。
sap+gap....
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 100

int map[MAXN][MAXN];
int h[MAXN];
int n,m;
int gap[MAXN];

bool f;

int sap(int v,int flow){
int rec=0,minh=n;
// printf("%d %d\n",v,flow);
// for (int i=0;i++<n+1;) printf("%d ",h[i]);
// printf("\n\n");
if (v==n+1){
f=true;
return flow;
}
for (int i=0;i++<n+1;){
if (map[v][i]){
if (h[i]==h[v]-1){
int ret=sap(i,min(flow-rec,map[v][i]));
map[v][i]-=ret;
map[i][v]+=ret;
rec+=ret;
if (flow==rec) return flow;
if (h[1]>=n+1) return rec;
}
minh=min(h[i],minh);
}
}
if (!f){
h[v]=minh+1;
}
if (!(--gap[h[v]])){
h[1]=n+1;
}

gap[h[v]]++;
return rec;
}

int main(){
int ans=0;
scanf("%d%d",&n,&m);
for (int i=0;i<=n+1;i++){
for (int j=0;j<=n+1;j++){
map[i][j]=0;
}
}
for (int i=0;i<=n+1;i++){
h[i]=0;
}
while (m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
map[x][y]+=z;
map[y][x]+=z;
}
scanf("%d",&m);
while (m--){
int x;
scanf("%d",&x);
map[x][n+1]=100000;
}
gap[0]=n+1;
while (h[1]<n+1){
f=false;
ans+=sap(1,0x7ffffff);
}
printf("%d\n",ans);
// system("pause");
return 0;
}

• @ 2012-08-01 19:25:36

注意是无向图啊、、、70分的自重啊、、、

• @ 2010-07-17 09:25:07

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2010-04-13 18:34:18

如楼下所言……赤裸裸的最小割……

第一遍没法显示无向图……结果70分

第二遍加了一句话AC

无语中……

至于最大流为什么等于最小割（最大流最小割定理），问问题的人可以想一下，如果把s和t看成两个集合……每条边就相当于一个门槛……而最小割就是那个最难逾越的门槛，所以流量一定是小于等于最小割的，即最大流等于最小割……

• @ 2010-03-11 20:22:42

裸的 - =

• @ 2010-03-11 20:20:35

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

很明显的最小割

• @ 2010-03-06 12:10:31

Accepted 有效得分：100 有效耗时：0ms

朴素网络流，设置超级汇点，求一遍原点1到超级汇点的最大流就好了

ID
1524

5

(无)

1316

468

36%

2