- 3 3
- 1 2 1
- 3 1 2
- 3 2 3
- #include<bits/stdc++.h>
- #define INF LLONG_MAX/2
- #define N 505
- using namespace std;
- struct ss
- {
- int v,next;
- long long flow;
- };
- int head[N],now_edge=0,S,T;
- ss edg[N*2];
- void init()
- {
- now_edge=0;
- memset(head,-1,sizeof(head));
- }
- void addedge(int u,int v,long long flow)
- {
- edg[now_edge]=(ss){v,head[u],flow};
- head[u]=now_edge++;
- edg[now_edge]=(ss){u,head[v],flow};
- head[v]=now_edge++;
- }
- int dis[N];
- int bfs()
- {
- memset(dis,0,sizeof(dis));
- queue<int>q;
- q.push(S);
- dis[S]=1;
- while(!q.empty())
- {
- int now=q.front();
- q.pop();
- for(int i=head[now];i!=-1;i=edg[i].next)
- {
- ss &e=edg[i];
- if(e.flow>0&&dis[e.v]==0)
- {
- dis[e.v]=dis[now]+1;
- q.push(e.v);
- }
- }
- }
- if(dis[T]==0)return 0;
- return 1;
- }
- int current[N];
- long long dfs(int x,long long maxflow)
- {
- if(x==T)return maxflow;
- for(int i=current[x];i!=-1;i=edg[i].next)
- {
- current[x]=i;
- ss &e=edg[i];
- if(e.flow>0&&dis[e.v]==dis[x]+1)
- {
- long long flow=dfs(e.v,min(maxflow,e.flow));
- if(flow!=0)
- {
- e.flow-=flow;
- edg[i^1].flow+=flow;
- return flow;
- }
- }
- }
- return 0;
- }
- long long dinic()
- {
- long long ans=0,flow;
- while(bfs())
- {
- for(int i=0;i<N;i++)current[i]=head[i];
- while(flow=dfs(S,INF))ans+=flow;
- }
- return ans;
- }
- int from[N],to[N],w[N];
- int main()
- {
- int n,m;
- scanf("%d %d",&n,&m);
- for(int i=1;i<=m;i++)
- {
- scanf("%d %d %d",&from[i],&to[i],&w[i]);
- }
- int ans=0;
- for(int i=1;i<=m;i++)
- {
- init();
- for(int j=1;j<=m;j++)
- if(w[j]<w[i])addedge(from[j],to[j],1);
- S=from[i];
- T=to[i];
- ans+=dinic();
- }
- printf("%d\n",ans);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2794410.html