分析：最大流的入门题，，BFS寻找增广路，找到则更新流量，直到找不到增广路为止。
#include<iostream>#include<queue>using namespace std;#define N 202#define MAX 0x7fffffff;class Max_Flow_EK{public:Max_Flow_EK(){}~Max_Flow_EK(){}int Run(int n,int m);private:void Init();void Read(int n);int MaxFlow(int s,int d,int m);int Bfs(int s,int d,int m);int m_iCap[N][N]; //记录残留网络的流量int m_iFlow[N];//从源点到当前节点还有当前流量可用int m_iPre[N];//增广路中节点的前驱queue<int> m_q;};int Max_Flow_EK::Run(int n,int m){Init();Read(n);return MaxFlow(1,m,m);}int Max_Flow_EK::Bfs(int s,int d,int m){int i,index;while(!m_q.empty()) m_q.pop(); //清空队列for(i=0;i<=m;i++)//初始化前驱m_iPre[i]=-1;m_iPre[s]=0;m_iFlow[s]=MAX;m_q.push(s);while(!m_q.empty()){index=m_q.front(); //取出队头节点m_q.pop();if(index==d)//找到了增光路break;for(i=1;i<=m;i++)if(i!=s && m_iCap[index][i]>0 && m_iPre[i]==-1){m_iPre[i]=index;m_iFlow[i]=m_iFlow[index]<m_iCap[index][i]?m_iFlow[index]:m_iCap[index][i];m_q.push(i);}}if(m_iPre[d]==-1) return -1;else return m_iFlow[d];}int Max_Flow_EK::MaxFlow(int s,int d,int m){int increasement;int sumflow;int k,last;sumflow=0;while((increasement=Bfs(s,d,m))!=-1){k=d;while(k!=s){last=m_iPre[k];m_iCap[last][k]-=increasement; //改变正向边容量m_iCap[k][last]+=increasement; //改变反向边容量k=last;}sumflow+=increasement;}return sumflow;}void Max_Flow_EK::Init(){memset(m_iCap,0,sizeof(m_iCap));memset(m_iFlow,0,sizeof(m_iFlow));}void Max_Flow_EK::Read(int n){int i;int Si,Ei,Ci;for(i=0;i<n;i++){scanf("%d %d %d",&Si,&Ei,&Ci);if(Si==Ei) continue;//起点可能与终点相同m_iCap[Si][Ei]+=Ci;//考虑重复输入}} int main() {int n,m;Max_Flow_EK max_flow;while(scanf("%d %d",&n,&m)==2){printf("%d\n",max_flow.Run(n,m));}return 0;}
与其在那里苦苦挣扎，碍于面子硬撑，倒不如微笑着面对，
