---恢复内容开始---
题意：
给了n个点，m条有向边。
接下来m行，每条边给起点终点与容量，以及一个标记。
标记为1则该边必须满容量，0表示可以在容量范围内任意流。
求：
从源点1号点到终点n号点的最小的可行流。
思路：
======================================================ge
1.二分最小可行流【是复杂度偏高的一种】
《一种简易的方法求解流量有上下界的网络中的网络流问题》
我自己的东西只有在二分的时候。判断当前枚举的值是偏大还是偏小其实是1号点与附加源点或者附加汇点的边的容量来看的。
坑点：
SGU的PE都是骗人的，很多WA的情况会显示成PE。大家不要被骗==
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define MAXN 4050
#define MAXM 40050
using namespace std;
const int inf=0x3f3f3f3f;
vector<pair<pair<int,int>,pair<int,int> > >jilu;
int inme[],outme[],n;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],sz;
void init()
{
sz=;
memset(G,-,sizeof(G));
}
void add_edge(int u,int v,int c)
{
E[sz]=Edge(v,c,,G[u]);
G[u]=sz++;
E[sz]=Edge(u,,,G[v]);
G[v]=sz++;
}
bool bfs(int S,int T)
{
static int Q[MAXN];
memset(dis,-,sizeof(dis));
dis[S]=;
Q[]=S;
for (int h=,t=,u,v,it; h<t; ++h)
{
for (u=Q[h],it=G[u]; ~it; it=E[it].nx)
{
if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
{
dis[v]=dis[u]+;
Q[t++]=v;
}
}
}
return dis[T]!=-;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=,tmp,v;
for (int &it=cur[u]; ~it&&ret<low; it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
ret+=tmp;
E[it].f+=tmp;
E[it^].f-=tmp;
}
}
}
if (!ret) dis[u]=-;
return ret;
}
int dinic(int S,int T)
{
int maxflow=,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G));
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
int check(){
bool ok=;
memcpy(cur,G,sizeof(G));
for(int i=;i<=n;i++){
if(ok==)break;
if(inme[i]-outme[i]>=){
for (int it=cur[]; ~it; it=E[it].nx){
int v=E[it].v;
if(v==i){
if(E[it].f!=E[it].c){
ok=;
}
break;
}
}
}
else{
for(int it=cur[i];~it;it=E[it].nx){
int v=E[it].v;
if(v==n+){
if(E[it].f!=E[it].c){
ok=;
}
break;
}
}
}
}
if(ok)return ;
if(inme[]>=outme[])
for(int it=cur[];~it;it=E[it].nx){
int v=E[it].v;
if(v==){
if(E[it].f==E[it].c){
return -;
}
else{
return ;
}
}
}
else
for(int it=cur[];~it;it=E[it].nx){
int v=E[it].v;
if(v==n+){
if(E[it].f==E[it].c){
return ;
}
else{
return -;
}
}
}
}
int main()
{
int m,sum1=,sum2=;
scanf("%d%d",&n,&m);
int a,b,c,d;
for(int i=;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a==)sum1+=c;
if(b==n)sum2+=c;
if(d)d=c;
inme[b]+=d;
outme[a]+=d;
jilu.push_back(make_pair(make_pair(a,b),make_pair(c,d)));
}
int l=,r=;
while(l<=r){
init();
int mid=(l+r)>>;
inme[]+=mid;
outme[n]+=mid;
for(int i=;i<m;i++){
a=jilu[i].first.first;
b=jilu[i].first.second;
c=jilu[i].second.first;
d=jilu[i].second.second;
add_edge(a,b,c-d);
}
for(int i=;i<=n;i++){
if(inme[i]>=outme[i]){
add_edge(,i,inme[i]-outme[i]);
}
else{
add_edge(i,n+,outme[i]-inme[i]);
}
}
dinic(,n+);
if(check()>=)r=mid-;
else l=mid+;
inme[]-=mid;
outme[n]-=mid;
}
init();
inme[]+=l;
outme[n]+=l;
for(int i=;i<m;i++){
a=jilu[i].first.first;
b=jilu[i].first.second;
c=jilu[i].second.first;
d=jilu[i].second.second;
add_edge(a,b,c-d);
}
for(int i=;i<=n;i++){
if(inme[i]>=outme[i]){
add_edge(,i,inme[i]-outme[i]);
}
else{
add_edge(i,n+,outme[i]-inme[i]);
}
}
dinic(,n+);
if(check()==){
printf("%d\n",l);
memcpy(cur,G,sizeof(G));
for(int i=;i<m;i++){
int u=jilu[i].first.first;
int v=jilu[i].first.second;
int c=jilu[i].second.second;
for(int it=cur[u];~it;it=E[it].nx){
if(E[it].v==v){
printf("%d",E[it].f+c);
if(i!=m-)printf(" ");
break;
}
}
}
printf("\n");
}
else{
puts("Impossible");
}
return ;
}
---恢复内容结束---