Sgu/176

//by hza
#include<cstdio>
 
const int INF=1<<29;
const int NUM=300;
const int MAXM=NUM*NUM;
 
int n,m;
int mx[NUM*NUM],my[NUM*NUM];
int C[NUM][NUM],B[NUM][NUM];
int W[NUM];
int right_num;
int S,T;
 
void init()
{
    int i,x,y,u,z;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d %d",&x,&y,&u,&z);
        C[x][y]=u;
        mx[i]=x;my[i]=y;
        if(z==1)
        {
            B[x][y]=u;
            W[y]+=u;W[x]-=u;
        }
        right_num+=u;
    }
}
 
int min(int a,int b){return a<b?a:b;}
 
int h[NUM],e[NUM];
int f[NUM][NUM];
int answer=0;
 
int sap(int u,int flow)
{
    if(u==T){answer+=flow;return flow;}
    int v,t,temp,remain=flow; 
    for(v=1;v<=T;++v)
    {
        if(h[v]+1==h[u]&&C[u][v]-f[u][v] >0)
        {
            temp=min(C[u][v]-f[u][v],remain);
            t=sap(v,temp);
            if(t)
            {
                f[u][v]+=t;f[v][u]-=t;
                remain-=t;
                if(remain==0)
                    return flow-remain;
            }
        }
    }
    if(h[S]>=n+2)return flow-remain;
    --e[h[u]];
    if(e[h[u]]==0)h[S]=n+2;
    ++e[++h[u]];
    return flow-remain;
}
 
int check(int k)
{
    B[n][1]=0;C[n][1]=k;
 
    int i,j;
 
    answer=0;        
    for(i=1;i<=T;++i)
        h[i]=e[i]=0;    
 
    for(i=1;i<=T;++i)
        for(j=1;j<=T;++j)
            f[i][j]=0;
 
    while(h[S]<T)
        sap(S,INF);
 
    for(i=1;i<=n;++i)
        if(f[S][i]!=W[i]&&f[i][T]!=-W[i])
            return 0;
    return 1;
}
 
void show(int k)
{
    B[n][1]=0;C[n][1]=k;
    int i,j;
 
    answer=0;        
    for(i=1;i<=T;++i)
        h[i]=e[i]=0;    
 
    for(i=1;i<=T;++i)
        for(j=1;j<=T;++j)
            f[i][j]=0;
 
    while(h[S]<T)
        sap(S,INF);
 
    for(i=1;i<=m;++i)
        printf("%d ",f[mx[i]][my[i]]+B[mx[i]][my[i]]);
    printf("\n");
}
 
void work()
{
    int i,j;
 
    S=n+1;T=n+2;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            C[i][j]-=B[i][j];
    for(i=1;i<=n;++i)
        if(W[i]>=0)
            C[S][i]=W[i];
        else C[i][T]=-W[i];
 
    right_num+=1;    
    int l=0,r=right_num,mid;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid;
    }
 
    int answer=r;
    if(check(l+1))answer=l+1;
    if(check(l))answer=l;
    if(answer==right_num)
    {
        printf("Impossible\n");
        return;
    }
    printf("%d\n",answer);
    show(answer);
}
 
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("176.in","r",stdin);freopen("176.out","w",stdout);
    #endif
    init();
    work();
}

/by Logic
#include<stdio.h>
#include<string.h>
const int maxn=120,maxm=10050,big=100000000;
int n,m,e[maxm][4],fl[maxn][maxn]={0};
int fl0[maxn][maxn],de[maxn][2]={0},sum=0;
int d[maxn]={0},gap[maxn]={0};
inline int min(int xx,int yy) {return xx<yy?xx:yy;}
int sap(int x,int flow)
{
	int i,p,t=flow;
	if(x==n+1) return flow;
	for(i=1;i<=n+1;i++)
		if(d[x]==d[i]+1&&fl0[x][i])
		{
			p=sap(i,min(fl0[x][i],t));
			fl0[x][i]-=p,fl0[i][x]+=p;
			if(!(t-=p)) return flow;
		}
	if(!(--gap[d[x]])) d[0]=n+2;
	++gap[++d[x]];
	if(d[0]>=n+2) return flow-t;
	return flow-t;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
#endif
	int i,j,c,l,r,mid,inf=0;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d%d",&e[i][1],&e[i][2],&e[i][3],&c);
		if(e[i][2]==n) inf+=e[i][3];
		if(c)
		{
			de[e[i][1]][1]+=e[i][3];
			de[e[i][2]][0]+=e[i][3];
		}
		else fl[e[i][1]][e[i][2]]=e[i][3];
	}
	for(i=1;i<=n;i++)
		if(de[i][0]-de[i][1]<0) fl[i][n+1]=de[i][1]-de[i][0],sum+=fl[i][n+1];
		else fl[0][i]=de[i][0]-de[i][1];
	l=0,r=inf+1;
	while(r>l)
	{
		int sum0=0;
		mid=(l+r)/2;
		memcpy(fl0,fl,sizeof(fl));
		fl0[n][1]=mid;
		memset(d,0,sizeof(d));
		memset(gap,0,sizeof(gap));
		for(gap[0]=n+2;d[0]<n+2;)
			sum0+=sap(0,big);
		if(sum0==sum) r=mid;
		else l=mid+1;
	}
	if(l>inf) {printf("Impossible\n");return 0;}
	memcpy(fl0,fl,sizeof(fl));
	fl0[n][1]=l;
	memset(d,0,sizeof(d));
	memset(gap,0,sizeof(gap));
	for(gap[0]=n+2;d[0]<n+2;)
		sap(0,big);
	printf("%d\n",l);
	for(i=0;i<m;i++)
		printf("%d ",e[i][3]-fl0[e[i][1]][e[i][2]]);
	return 0;
}