乍一看貌似和运输问题1没有任何区别，但本题有一个有意思的东西叫做下限，我个人称之为非强制下限，因为本题中要求的实际是我走这条边这条边才至少走下限的流，虽然出题人没说，但从样例来看确实是这样的，而强制下限目前还没做到，有待更新……
其实这道题还是板子，唯一与1不同的是它对建边提出了其他要求。即将边拆成三部分将原来u->v的流量设为上限-下限，s->v，u->t，流量为下限，详见刘汝佳《算法奥赛入门经典训练指南》（俗称蓝书）。至于s->v,u->t,直接统计一下，最后一起结算便是。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 int n,zz=1,a[110]; 10 struct ro{ 11 int to; 12 int next; 13 int l; 14 int from; 15 }road[40004]; 16 void build(int x,int y,int z){ 17 zz++; 18 road[zz].l=z; 19 road[zz].from=x; 20 road[zz].to=y; 21 road[zz].next=a[x]; 22 a[x]=zz; 23 zz++; 24 road[zz].to=x; 25 road[zz].from=y; 26 road[zz].next=a[y]; 27 a[y]=zz; 28 } 29 int ss,tt; 30 int pre[110],flow[110]; 31 queue q1; 32 int bfs(int s,int t){ 33 memset(pre,-1,sizeof(pre)); 34 memset(flow,0x7f,sizeof(flow)); 35 int tt=flow[0]; 36 pre[s]=0; 37 q1.push(s); 38 while(!q1.empty()) 39 { 40 int x=q1.front();q1.pop(); 41 for(int i=a[x];i>0;i=road[i].next) 42 { 43 int y=road[i].to; 44 if(pre[y]!=-1||road[i].l<=0)continue; 45 pre[y]=i; 46 flow[y]=min(flow[x],road[i].l); 47 q1.push(y); 48 } 49 } 50 if(flow[t]==tt)return -1; 51 else return flow[t]; 52 } 53 int sum; 54 int work(int s,int t){ 55 int ans=0; 56 while(1) 57 { 58 int x=bfs(s,t); 59 if(x==-1)break; 60 ans+=x; 61 int now=pre[t]; 62 while(now) 63 { 64 road[now].l-=x; 65 road[now^1].l+=x; 66 now=pre[road[now].from]; 67 } 68 } 69 return ans; 70 } 71 int s[105]; 72 int main(){ 73 freopen("maxflowb.in","r",stdin); 74 freopen("maxflowb.out","w",stdout); 75 scanf("%d",&n); 76 tt=n+1; 77 for(int i=1;i<=n;i++) 78 { 79 for(int j=1;j<=n;j++) 80 { 81 int x,y; 82 scanf("%d%d",&x,&y); 83 if(!y) continue; 84 s[i]-=x; 85 s[j]+=x; 86 build(i,j,y-x); 87 } 88 } 89 build(n,1,0x7fffffff); 90 for(int i=1;i<=n;i++) 91 { 92 if(s[i]>0) 93 { 94 build(ss,i,s[i]); 95 } 96 else if(s[i]<0) 97 { 98 build(i,tt,-s[i]); 99 }100 }101 int an=work(ss,tt);102 int anss=work(1,n);103 printf("%d\n",anss);104 //while(1);105 return 0;106 }
代码挺丑，请谅解。