chyx's Blog

#include <cmath>
using namespace std;
#include <numeric>
#include <functional>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>

//By chyx111
typedef pair<int,int> pii;
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)

const int MAXN = 128;
int G[ MAXN ][ MAXN ], flow[ MAXN ], pnt[ MAXN ];
int add[ MAXN ][ MAXN ];

// E是具体题目的数据，与模板无关
int E[ MAXN*MAXN ][ 3 ];

bitset< MAXN > mk;
int oo = 0x0f0f0f0f;
int n, m;

int augment(){
	mk.reset();
	memset(flow,0,(sizeof flow));
	flow[0] = oo;
	priority_queue<pii> Q;
	Q.push( pii(oo,0) );
	mk.reset();
	while( !Q.empty() ){
		int cur = Q.top().second; Q.pop();
		mk[cur] = true;
		if( cur == n+1){
			for(int i = cur; i != 0; i = pnt[i] ){
				G[pnt[i]][i] -= flow[n+1];
				G[i][pnt[i]] += flow[n+1];
	
				add[pnt[i]][i] += flow[n+1];
				add[i][pnt[i]] -= flow[n+1];
			}
			return flow[n+1];
		}
		for(int i = 1; i <= n+1; ++i)if( !mk[i] && G[cur][i] && flow[i] < G[cur][i] && flow[i] < flow[cur] ){
			flow[i] = min( flow[cur], G[cur][i] );
			pnt[i] = cur;
			Q.push( pii(flow[i], i ) );
		}
	}
	return 0;
}

int maxflow(){
	int add;
	int ans = 0;
	while( add = augment() ){
//		cout << "augment: " << add << endl;
		ans += add;
	}
	return ans;
}

int main() {
	while(cin >> n >> m){
		memset(G,0,(sizeof G));
		memset(add,0,(sizeof add));
		G[0][1] = oo;
		G[n][n+1] = oo;
		Rep(i,m){
			int a, b, c, d;
			scanf("%d%d%d%d", &a, &b, &c, &d);
			E[i][0] = a; E[i][1] = b; E[i][2] = c;
			if(d){
				G[0][b] += c;
				G[a][n+1] += c;
			}else{
				G[a][b] = G[b][a] = c;
				E[i][2] = 0;
			}
		}
		bool ok = true;
		int flow = maxflow(); 
		if( count( G[0]+2, G[0]+n+1, 0 ) != n-1) ok = false;

		if( ok ){
			cout << add[0][1] << endl;
			Rep(i,m){
				if(i) putchar(' ');
				printf("%d", E[i][2] + max(add[E[i][0]][E[i][1]],add[E[i][1]][E[i][0]]));
			}
			puts("");
		}else{
			puts("Impossible");
		}
	}
	return 0;
}