69 条题解
-
2
Sky1231 (sky1231) LV 10 @ 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)); } } -
1
Nightingalelyy LV 10 @ 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 head[100001], dis[100001], cur[100001]; int n, m, i, j, k, l, tot=-1, ans, total,t,s; inline int read() { 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; g[tot].next = head[u]; head[u] = tot; } 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() { n = read(); m = read(); memset(head, -1, sizeof(head)); s = 1; t = n + 1; for (int i = 1;i <= m;i++) { int u, v, w; u = read(); v = read(); w = read(); addedge(u, v, w); addedge(v, u, w); } int e = read(); for (i = 1;i <= e;i++) { int k; k = read(); addedge(k, t, maxn); } while (bfs()) { for (i = 0;i <= t;i++) cur[i] = head[i]; int tans = dfs(s, maxn); ans += tans; } printf("%d\n", ans); system("pause"); return 0; } -
1
感谢前辈！
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;
}
``` -
0
测试数据 #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);
D.AddEdge(a, b, c,0);
D.AddEdge(b, a, c, 0);
}
int m, aa;
scanf("%d", &m);
For(0, m){
scanf("%d", &aa);
D.AddEdge(aa, n + 1, INF,0);
}
printf("%d\n", D.MaxFlow(1, n + 1));return 0;
}
``` -
0
这题在点 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);
#endifEdmondsKarp 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;
ek.AddEdge(a, b, w);
ek.AddEdge(b, a, w);
}
int m; cin >> m;
for (int i = 0; i < m; ++i) {
cin >> a;
ek.AddEdge(a, n+1, INF);
}
cout << ek.Maxflow(1, n+1) << endl;
return 0;
} -
0
用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;
}
-
0
最大流最小割，注意无向双边。
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);
add_edges(a,b,w);
add_edges(b,a,w);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int k;
scanf("%d",&k);
add_edges(k,n+1,INF);
}int ans=Dinic();
printf("%d\n",ans);
return 0;
}/* Accepted, time = 30 ms, mem = 648 KiB, score = 100 2016年6月21日星期二 */
``` -
0
caesar_199 LV 9 @ 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];
int head = 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[head] = u;
front[u] = 0;
next[u] = head;
head = u;
}
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;
add (temu, temv, temw);
add (temv, temu, 0);
add (temv, temu, temw);
add (temu, temv, 0);
}
s = 1;
t = n + 1;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> temu;
add (temu, t, inf);
add (t, temu, 0);
}
init (s);
rtf (s, t);
for (int i = 0; i < g[s].size(); i++) {
maxf += edges[g[s][i]].f;
}
cout << maxf;
return 0;
}
``` -
0
令人振奋，第一道网络流就一遍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));
int head=1,tail=2;
q[1]=1;
tag[1]=1;
while (head<tail) {
if (q[head]==0)
return 1;
for (int i=1,u=q[head],v;i<=edge[q[head]][0];i++) {
v=edge[q[head]][i];
if (tag[v]==0 && map[u][v]>0) {
q[tail++]=v;
tag[v]=tag[u]+1;
}
}
head++;
}
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;
} -
0
1263659722 LV 10 @ 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];
void add(int x,int y,int z)
{
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);
add(a,b,c);
add(b,a,c);
}
s=1;
t=n;
scanf("%d",&w);
for(int i=1;i<=w;i++)
{
int tx;
scanf("%d",&tx);
add(tx,t,1<<29);
}
printf("%d",solve());
return 0;
} -
0
大神说最大流过了，算法就入门了 好激动。。。楼下说的很不错，提供一个dfs找增广路代码
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;int n, e;
int End;
#define INF 100000000
// end = n+1struct edge {
int from, to, dis;
int next;
} edges[1000];
int pos = 0;
int head[1000];
bool markedUnlink[1000];
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;
edges[pos].next = head[from];
head[from] = pos;
}
////////////////////////////////////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;
}
}
markedUnlink[from] = true;
return 0;
}int maxFlow()
{
int anslength = 0;
while (1) {
int addlength = dfsFindPath(1);
while (!edgeSub.empty()) {
edges[edgeSub.top()].dis -= addlength;
edgeSub.pop();
}
if (addlength == 0)
return anslength;
anslength += addlength;
}
}int main()
{
memset (head,0,sizeof(head));
memset (markedUnlink,0,sizeof(markedUnlink));
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;
} -
0
裸最小割 根据最小割最大流定理 就是求最大流，建立一个超级汇点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;void add(int from,int to,int cap){
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);
for(int i=1;i<=e;i++) scanf("%d%d%d",&a,&b,&w),add(a,b,w),add(b,a,w);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&a),add(a,n+1,INF);
s=1,t=n+1;
ans=maxflow();
printf("%d",ans);
return 0;
} -
0
编译成功
测试数据 #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;
} -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
zhanghanyuan LV 10 @ 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
很明显的最小割
Sky1231 (sky1231)
LV 10
@ 2017-07-08 22:05:01
