他人博客详细讲解:http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html

1.被人调戏找哥哥2.想调戏人找哥哥3.受欺负找哥哥4.想欺负人找哥哥5.挨骂找哥哥6.哭诉找哥哥7.怕鬼找哥哥8.做错事找哥哥9.没钱找哥哥10.生病找哥哥11.软萌找哥哥12.装逼找哥哥13.炸毛找哥哥14.傲娇找哥哥15.生气找哥哥16.单身找哥哥17.换情头找哥哥18.秀恩爱找哥哥19.弧了找哥哥20.解决问题找哥哥21.写作业找哥哥22.起床找哥哥23.睡觉找哥哥24.么么找哥哥25.依赖找哥哥26.信任找哥哥27.要礼物找哥哥28.没流量找哥哥29.没WiFi找哥哥30.求安慰找哥哥31.宠爱找哥哥32.买东西找哥哥33.饿了找哥哥34.出门找哥哥35.无聊找哥哥36.在学校找哥哥37.被告白找哥哥38.告白找哥哥39.心塞找哥哥40.软弱找哥哥41.有心结找哥哥42.坏毛病找哥哥43.闯祸找哥哥44.结婚找哥哥45.发呆找哥哥46.没饭吃找哥哥47.做饭找哥哥48.顽皮找哥哥49.固执找哥哥50.天塌了找哥哥51.太阳不见了找哥哥52.爆照找哥哥53中二找哥哥54.花痴找哥哥55.吐槽找哥哥56.话废找哥哥57.话唠找哥哥58.求安利找哥哥59.安利找哥哥60.看电视找哥哥61.买东西找哥哥62.交朋友找哥哥63.失恋找哥哥64.失眠找哥哥65.熬夜找哥哥66.早睡找哥哥67.开心找哥哥68.伤心找哥哥69.被勾搭找哥哥70.勾搭找哥哥71.看番找哥哥72.看电影找哥哥73.想哭找哥哥74.发泄找哥哥74.写信找哥哥75.路痴找哥哥76.坐车找哥哥77.学车找哥哥78.烦恼找哥哥79.听歌找哥哥80.要图找哥哥81.炫耀找哥哥82.求鼓励找哥哥83.有需求找哥哥84.胃疼找哥哥85.摔了找哥哥86.过节找哥哥88.过年找哥哥89过生日找哥哥90.饱了找哥哥91.胖了找哥哥92.出气找哥哥93.看小说找哥哥94.求资源找哥哥95.看恐怖片找哥哥96.世界末日找哥哥97.火山爆发找哥哥98.地震火灾找哥哥99.有事找哥哥100.没事找哥哥以下省略两百条……反正哥哥是多功能的,哦不~是万能的

好像大概意思是不停地用bfs找一条增广链,并更新答案,直到找不到为止,构图时需构建反向弧,来让错误的路可以往回走。。

程序:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
struct ding{
   int from,to,cap,now;
};
int a[20000],p[20000];
vector<ding>edge;
vector<int>g[20000];
int esize=0,n,m;
void add(int from1,int to1,int val)
{
  edge.push_back((ding){from1,to1,val,0});
  edge.push_back((ding){to1,from1,0,0});
  g[from1].push_back(esize);
  g[to1].push_back(esize+1);
  esize+=2;
}
int maxlow(int s,int t)
{
  int ans=0;
  while (true)
  {
      queue<int>q;
      q.push(s);
      memset(a,0,sizeof a);
      a[s]=2100000000;
      while (!q.empty())
      {
        int k=q.front(); q.pop();
      for (int i=0;i<=g[k].size()-1;i++)
      {
          ding enow=edge[g[k][i]];
          if ((a[enow.to]==0)&&(enow.now<enow.cap))
          {
            a[enow.to]=min(a[k],enow.cap-enow.now);
          p[enow.to]=g[k][i];
          q.push(enow.to);    
        }
      }     
      if (a[t]) break;
    }
    if (!a[t]) break;
    ans+=a[t];
    for (int i=t;i!=s;i=edge[p[i]].from)
    {
      edge[p[i]].now+=a[t];
      edge[p[i]^1].now-=a[t];
    }
  }
  return ans;
}
int main()
{
  int s,t,u,v,w;
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for (int i=1;i<=m;i++) 
  {
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w);
  }
  printf("%d\n",maxlow(s,t));
  return 0;
} 

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注