題意：

裸的最大流。

?

思路：

先試了一下紅書模板，TLE了，想起來那個比較快的模板，直接就過了。。。果然模板的質量也是不一樣的。

?

代碼：

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<queue> #include<stack> #include<set> #include<string> #include<vector>using namespace std; const int maxn = 510, maxm = maxn * maxn; const int inf = 1000000000;class MaxFlow//一個挺快的模板,比一般的MaxFlow快,我也不知道為什么。。。 { private:int next[maxm*2];int num[maxm*2];int a[maxn*2];int row_sum[maxn];int col_sum[maxn];int n , m, K;int d[maxn*2], st[maxn*2], cod[maxn][maxn];int h[maxn*2], vh[maxn*2];bool don[maxm*2],in[maxn*2];int dfs(int, int);bool visit(int, int); public:int T;int r[maxm*2];MaxFlow() {}int Addedge(int, int, int);int Run();bool FindCircle();void Init(int m){memset(a, 0, sizeof(a));tt = 1;T = m;}int tt;~MaxFlow() {} } mf;int MaxFlow::Addedge(int x,int y,int rr) {next[++tt]=a[x];num[tt]=y;r[tt]=rr;a[x]=tt;next[++tt]=a[y];num[tt]=x;r[tt]=0;a[y]=tt;return tt; }int MaxFlow::dfs(int x,int y) {if (x==T) return y;int sig=st[x],minh=T+1;do{if (r[st[x]]){if (h[num[st[x]]]+1==h[x]){int k=dfs(num[st[x]],min(y,r[st[x]]));if (k){r[st[x]]-=k;r[st[x]^1]+=k;return k;}}minh=min(minh,h[num[st[x]]]+1);if (h[0]>T) return 0;}st[x]=next[st[x]];if (st[x]==0) st[x]=a[x];}while (sig!=st[x]);if (vh[h[x]]--==0) h[0]=T+1;vh[h[x]=minh]++;return 0; }int MaxFlow::Run() {for (int i=0; i<=T; i++) h[i]=vh[i]=0;for (int i=0; i<=T; i++) st[i]=a[i];vh[0]=T+1;int ret=0;while (h[0]<=T) ret+=dfs(0,K+1);return ret; }bool MaxFlow::visit(int x,int ed) {if (don[ed])return in[x];don[ed]=true;in[x]=true;for (int p=a[x]; p; p=next[p]){if (r[p] && (ed^p)!=1)if (visit(num[p],p)) return true;}in[x]=false;return false; }bool MaxFlow::FindCircle() {for (int i=0; i<=T; i++) in[i]=false;for (int i=1; i<=tt; i++) don[i]=false;for (int i=2; i<=tt; i++){if (r[i] && !don[i]){in[num[i^1]]=true;if (visit(num[i],i)) return true;in[num[i^1]]=false;}}return false; }int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){int t=m;mf.Init(t);mf.Addedge(0,1,inf);for(int i=1;i<=n;i++){int s,t,c;scanf("%d%d%d",&s,&t,&c);mf.Addedge(s,t,c);}int ans=mf.Run();printf("%d\n",ans);}return 0; }

另附上紅書TLE模板：

?

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<queue> #include<stack> #include<set> #include<string> #include<vector>using namespace std; const int maxn = 510, maxm = maxn * maxn; const int inf = 1000000000;struct Edge {int v,f,nxt; };int n,src,sink; int g[maxn+10]; int nume; Edge e[maxm*2+10];void addedge(int u,int v,int c) {e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume;e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume; }void init() {memset(g,0,sizeof g);nume=1; }queue<int> que; bool vis[maxn+10]; int dist[maxn+10];void bfs() {memset(dist ,0,sizeof dist);while(!que.empty())que.pop();vis[src]=true;que.push(src);while(!que.empty()){int u=que.front();que.pop();for(int i=g[u];i;i=e[i].nxt)if(e[i].f&&!vis[e[i].v]){que.push(e[i].v);dist[e[i].v]=dist[u]+1;vis[e[i].v]=true;}} }int dfs(int u,int delta) {if(u==sink){return delta;}else {int ret=0;for(int i=g[u];delta&&i; i=e[i].nxt)if(e[i].f&&dist[e[i].v]==dist[u]+1){int dd=dfs(e[i].v,min(e[i].f,delta));e[i].f-=dd;e[i^1].f+=dd;ret+=dd;}return ret;} }int maxflow() {int ret=0;while(true){memset(vis,0,sizeof vis);bfs();if(!vis[sink])return ret;ret+=dfs(src,inf);} }int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){init();src=1;sink=m;for(int i=1;i<=n;i++){int s,t,c;scanf("%d%d%d",&s,&t,&c);addedge(s,t,c);}int ans=maxflow();printf("%d\n",ans);}return 0; }

?

?

?

?

?

總結

以上是生活随笔為你收集整理的hdu1532(最大流裸题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。