一、有上下界的网络流：
sgu 194 （无源汇的上下界网络流）：
题意：给出一个网络，每条边有上下界，问是否存在可行流。如果存在，输出经过每条边的流量。
建图：每条边必须有li的流量，那么新建超级源点和超级汇点，然后统计每个点的“入度”和“出度”，然后源点和每个点建一条流量为“入度”的边，每个点和汇点建一条流量为“出度”的边。为了流量平衡，每条边取原有上界-原有下界为流量，然后加入网络。（还有种做法是每个点统计出度和入度，判断是正是负来决定它和源点还是汇点建边。这种做法运行效率更高一些。）
题目给的图因为没有源点和汇点，所以我觉得统计最大流是没有意义的。对于我们自己建的图，判断一下每条边的下界的和是否等于最大流，以此来判定是否有可行流就行了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <ctime>
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
#define req(i,l,n) for(int i=(l);i<(n);i++)
using namespace std;
typedef long long LL;
const int maxn=205+1,maxm=120000;
const LL jx=0x7fffffffffffffff;
int pos,ta[maxn],lin[maxm],sd[maxm],sl[maxm];
void biu(int s,int t,int c)
{
++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;
++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;
}
int nn;
int h[maxn];
int vh[maxn];
int aug(int v,int deta)
{
if (v==nn) return deta;
int mins=nn-1,augc,bak=deta;
for (int i=ta[v];i;i=lin[i])
if (sl[i])
{
if (h[v]==h[sd[i]]+1)
{
augc=min(deta,sl[i]);
augc=aug(sd[i],augc);
deta-=augc;
sl[i]-=augc; sl[(i+1^1)-1]+=augc;
if (!deta) break;
if (h[nn-1]>=nn) return bak-deta;
}
mins=min(mins,h[sd[i]]);
}
if (bak==deta)
{
vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;
h[v]=mins+1; vh[h[v]]++;
}
return bak-deta;
}
int n,m;
int rd[201],cd[201];
int pipel[maxm];
int main(){
scanf("%d%d",&n,&m);
int u,v,l,c;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&u,&v,&l,&c);
pipel[i]=l;
rd[v]+=l; cd[u]+=l;
biu(u,v,c-l);
}
nn=n+2;//--
LL sum=0;
for (int i=1;i<=n;i++)
{
if (rd[i]) biu(nn-1,i,rd[i]);
if (cd[i]) biu(i,nn,cd[i]);
sum+=rd[i];
}
LL flow=0;
while (h[nn-1]<nn) flow+=aug(nn-1,0x7fffffff);
if (sum!=flow) puts("NO
");
else
{
puts("YES");
for (int i=1;i<=m;i++) printf("%d
",pipel[i]+sl[i*2]);
}
return 0;
}
（提示：如果第7个点WA了，说明你没开long long或者数组范围没够。）
Regionals 2013 - Europe - Southwestern - It Can Be Arranged （有源汇的上下界网络流最小流）：
大致思路是先弄成无源汇，然后跑一遍maxflow，这样就能保证下界是满足的了。并且因为刚好是满足下界的，所以这样的网络流是最小流。这个最小流指的是在网络中流动的，而不是说的从源点到汇点的最小流。
这题要注意的是，连边（汇点，源点）后，虽能算出源点到汇点的可行流，但它不是最小流。原因是在还没有充分利用网络中的边时，就使用了（汇点，源点）这条边，于是就导致答案偏大。（这里有个很形象的图）
解决方法是先跑一遍maxflow，使之充分利用网络中的边，然后再加上（汇点，源点）这条边，再跑一遍maxflow，就求出了最小流。
这道题因为无上界，必然有可行流，所以就免了上一道题sigma(度数)==flow的判断。
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define FORD(i,r,l) for (int i=(r);i>=(l);i--)
using namespace std;
const int maxn=205+1,maxm=120000,jx=0x7fffffff;
int pos,ta[maxn],lin[maxm],sd[maxm],sl[maxm];
void biu(int s,int t,int c)
{
++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;
++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;
}
int nn;
int h[maxn];
int vh[maxn];
int aug(int v,int deta)
{
if (v==nn) return deta;
int mins=nn-1,augc,bak=deta;
for (int i=ta[v];i;i=lin[i])
if (sl[i])
{
if (h[v]==h[sd[i]]+1)
{
augc=min(deta,sl[i]);
augc=aug(sd[i],augc);
deta-=augc;
sl[i]-=augc; sl[(i+1^1)-1]+=augc;
if (!deta) break;
if (h[nn-1]>=nn) return bak-deta;
}
mins=min(mins,h[sd[i]]);
}
if (bak==deta)
{
vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;
h[v]=mins+1; vh[h[v]]++;
}
return bak-deta;
}
int n,m;
int A[101],B[101],S[101];
int clean[101][101];
int rd[101*2],cd[101*2];
void init(int nn)
{
pos=0;
for (int i=0;i<=nn;i++) ta[i]=h[i]=vh[i]=0;
for (int i=1;i<=n*2;i++) rd[i+n]=cd[i]=0;
}
void make_graph()
{
init(n*2+4);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (B[i]+clean[i][j]<A[j])//?
biu(i+n,j,jx);
nn=n*2+2;
for (int i=1;i<=n;i++) biu(nn-1,i,jx),biu(i+n,nn,jx);
for (int i=1;i<=n;i++)
{
rd[i+n]+=(S[i]-1)/m+1;
cd[i]+=(S[i]-1)/m+1;
biu(i,i+n,jx);
}
nn+=2;
for (int i=1;i<=n;i++) biu(i,nn,cd[i]),biu(nn-1,i+n,rd[i+n]);
}
int solve()
{
int sum=0,flow=0;
make_graph();
while (h[nn-1]<nn) flow+=aug(nn-1,jx);
for (int i=1;i<=n;i++) sum+=cd[i];
if (sum!=flow)
{
memset(h,0,sizeof(h));
memset(vh,0,sizeof(vh));
biu(nn-2,nn-3,jx);
while (h[nn-1]<nn) aug(nn-1,jx);
}
int ans=0;
nn-=2;
for (int i=ta[nn-1];i;i=lin[i])
if (sd[i]==nn)
{
ans=sl[i];
break;
}
return ans;
}
int main(){
for (int T;scanf("%d",&T)!=EOF;)
for (int tt=1;T--;tt++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d%d%d",A+i,B+i,S+i);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&clean[i][j]);
printf("Case %d: %d
",tt,solve());
}
return 0;
}
zoj 3229 （有源汇的上下界网络流最大流）：
这种题与上面两种题型的不同在于在判断是否存在可行流之后，我们要删除超级汇点和超级源点，还要把（汇点，源点）这条边删去，再从源点到汇点进行一次maxflow。
这题建图很好想。比较坑的是输出的地方描述不好懂。
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define FORD(i,r,l) for (int i=(r);i>=(l);i--)
using namespace std;
const int maxn=1400,maxm=160000,jx=0x7fffffff;
int pos,ta[maxn],lin[maxm],sd[maxm],sl[maxm];
void biu(int s,int t,int c)
{
++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;
++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;
}
int nn;
int h[maxn];
int vh[maxn];
int aug(int v,int deta)
{
if (v==nn) return deta;
int mins=nn-1,augc,bak=deta;
for (int i=ta[v];i;i=lin[i])
if (sl[i])
{
if (h[v]==h[sd[i]]+1)
{
augc=min(deta,sl[i]);
augc=aug(sd[i],augc);
deta-=augc;
sl[i]-=augc; sl[(i+1^1)-1]+=augc;
if (!deta) break;
if (h[nn-1]>=nn) return bak-deta;
}
mins=min(mins,h[sd[i]]);
}
if (bak==deta)
{
vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;
h[v]=mins+1; vh[h[v]]++;
}
return bak-deta;
}
int n,m;
int G[maxn];
int rd[maxn],cd[maxn];
int sum;
int gra[maxn][maxn]; bool id[maxn][maxn];
void init()
{
//init
pos=0;
for (int i=1;i<=n+m+4;i++) ta[i]=h[i]=vh[i]=rd[i]=cd[i]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) gra[i][j]=id[i][j]=0;
//make graph
nn=n+m+2;
for (int i=1;i<=m;i++)
{
scanf("%d",G+i);
rd[nn]+=G[i]; cd[n+i]+=G[i];
biu(i+n,nn,jx);
}
int c,d,t,l,r;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&c,&d);
biu(nn-1,i,d);
for (int j=1;j<=c;j++)
{
scanf("%d%d%d",&t,&l,&r); t++;
cd[i]+=l; rd[t+n]+=l;
biu(i,t+n,r-l);
gra[i][t]+=l; id[i][t]=1;
}
}
nn+=2; sum=0;
for (int i=1;i<=n+m+2;i++)
if (cd[i]>rd[i]) biu(i,nn,cd[i]-rd[i]),sum+=cd[i]-rd[i];
else if (rd[i]>cd[i]) biu(nn-1,i,rd[i]-cd[i]);
biu(nn-2,nn-3,jx);//make cycle
}
void solve()
{
nn-=2;
int flow=sl[ta[nn-1]];
ta[nn]=lin[ta[nn]]; ta[nn-1]=lin[ta[nn-1]];
for (int i=1;i<=nn;i++) h[i]=vh[i]=0;
while (h[nn-1]<nn) flow+=aug(nn-1,jx);
printf("%d
",flow);
for (int v=n+1;v<=n+m;v++)
for (int i=ta[v];i;i=lin[i])
if (sd[i]>=1&&sd[i]<=n)
gra[sd[i]][v-n]+=sl[i];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (id[i][j])
printf("%d
",gra[i][j]);
}
int main(){
for (;scanf("%d%d",&n,&m)!=EOF;)
{
init();
int flow=0;
while (h[nn-1]<nn) flow+=aug(nn-1,jx);
if (flow!=sum) puts("-1");
else solve();
puts("");
}
return 0;
}
——至此，上下界网络流题型算是补完了。
二、01分数规划：
poj 3155 Hard Life（最大密度子图）：
这是道坑题...把二分的精度从1e-8调到1e-6就能AC了...个中原因还需研究一下...
//13395616 ooyyloo 3155 Accepted 840K 282MS G++ 2963B 2014-08-30 12:33:29
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=11002+1,maxm=120000;
const double inf=1000000.0;
const double eps=1e-18;
int pos,ta[maxn],lin[maxm],sd[maxm]; double sl[maxm];
void biu(int s,int t,double c)
{
++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; sl[pos]=c;
++pos; lin[pos]=ta[t]; ta[t]=pos; sd[pos]=s; sl[pos]=0;
}
int nn;
int h[maxn],vh[maxn];
double aug(int v,double deta)
{
if (v==nn) return deta;
int mins=nn-1; double augc,bak=deta;
for (int i=ta[v];i;i=lin[i])
if (sl[i]>0.0)
{
if (h[v]==h[sd[i]]+1)
{
augc=min(deta,sl[i]);
augc=aug(sd[i],augc);
deta-=augc;
sl[i]-=augc; sl[(i+1^1)-1]+=augc;
if (deta<=0) break;
if (h[nn-1]>=nn) return bak-deta;
}
mins=min(mins,h[sd[i]]);
}
if (bak==deta)
{
vh[h[v]]--; if (vh[h[v]]==0) h[nn-1]=nn;
h[v]=mins+1; vh[h[v]]++;
}
return bak-deta;
}
int n,m;
int edge[1001][2];
bool vis[maxn];
void init()
{
pos=0;
for (int i=1;i<=nn;i++) ta[i]=h[i]=vh[i]=0;
}
void make_graph(double x)
{
nn=n+m+2;
init();
for (int i=1;i<=m;i++)
{
biu(nn-1,i,1.0);
biu(i,edge[i][0]+m,inf);
biu(i,edge[i][1]+m,inf);
}
for (int i=1;i<=n;i++) biu(i+m,nn,x);
}
int ans;
void dfs(int v)
{
vis[v]=1;
if (v>m&&v<=m+n) ans++;
for (int i=ta[v];i;i=lin[i])
if (sl[i]>0)
if (!vis[sd[i]]) dfs(sd[i]);
}
void solve()
{
/*double flow=0; make_graph(1.25);
while (h[nn-1]<nn) flow+=aug(nn-1,inf);
cout<<flow<<endl;*/
double l=0,r=m,mid,gap=1.0/n/n/10;
double flow;
while (r-l>=1e-6)
{
mid=(l+r)/2;
flow=m; make_graph(mid);
while (h[nn-1]<nn) flow-=aug(nn-1,inf);
if (flow==0.0) r=mid; else l=mid;
}
make_graph(l);
while (h[nn-1]<nn) aug(nn-1,inf);
ans=0;
for (int i=1;i<=nn;i++) vis[i]=0;
dfs(nn-1);
/*for (int i=ta[nn];i;i=lin[i])
if (sl[i]==l)//?
if (!vis[sd[i]-m])
vis[sd[i]-m]=1,ans++;*/
printf("%d
",ans);
for (int i=1;i<=n;i++)
if (vis[i+m])
printf("%d
",i);
}
int main(){
for (;scanf("%d%d",&n,&m)!=EOF;)
{
for (int i=1;i<=m;i++)
scanf("%d%d",&edge[i][0],&edge[i][1]);
if (!m) printf("1
1
");
else solve();
}
return 0;
}