chyx's Blog

namespace geometry{
	typedef complex<double> Pt;
	double eps = 1e-10;
#define X real()
#define Y imag() // Not real(), don't forget it when copy and paste
	template<class T> T ccw(const complex<T>& a, const complex<T>& b){
		return imag( conj(a) * b );
	}
	int sign(double x){
		return fabs(x) < eps ? 0 : x < 0 ? -1 : 1;
	}

	//直线相交
	void line_abc(Pt s, Pt t, double &a, double &b, double &c){
		// a x + b y + c == 0
		// s.X * ( s.Y - t.Y ) - s.Y * ( s.X - t.X ) + ccw(s,t) == 0
		a = s.Y - t.Y;
		b = -(s.X - t.X);
		c = ccw(s,t);
	}
	// 两直线交点
	char inter_line(Pt a, Pt b, Pt c, Pt d, Pt &p){
		typedef T double;
		T a1, b1, c1, a2, b2, c2;
		line_abc(a,b,a1,b1,c1);
		line_abc(c,d,a2,b2,c2);
		// 二元一次方程组
		// [a1 b1 c1]
		// [a2 b2 c2]
		T d = a1 * b2 - a2 * b1;
		if( !sign(d) ) return ( !sign(a1*c2-a2*c1) && !sign(b1*c2-b2*c1) ) ? '-' : '='; // 平行或重合
		p = Pt( (b1*c2-b2*c1) / d, -(a1*c2-a2*c1) / d );
		return 'x';
	}
	// 两线段交点
	char inter_seg(Pt a, Pt b, Pt c, Pt d, Pt &p){
#define SERPARATE(a,b,c,d,X) sign( max(a.X,b.X), min(c.X,d.X) ) < 0
#define T double
		if( SERPARATE(a,b,c,d,X) ||
				SERPARATE(a,b,c,d,Y) ||
				SERPARATE(c,d,a,b,X) ||
				SERPARATE(c,d,a,b,Y) ){
			return '0'; // 不相交
		}
		T u1 = ccw(b-a,c-a), u2 = (b-a,d-a);
		T u3 = ccw(d-c,a-c), u4 = (d-c,b-c);
		int bac = sign(u1), bad = sign(u2);
		int dca = sign(u3), dcb = sign(u4);
		if( bac * bad > 0 ) return '0';
		if( dca * dcb > 0 ) return '0';
		if( bac * bad < 0 && dca * dcb < 0 ){
			p.X = ( c.X * u2 - d.X * u1 ) / ( u2 - u1 );
			p.Y = ( c.Y * u2 - d.Y * u1 ) / ( u2 - u1 );
			return 'x'; //规范相交
		}
		if( !bac && !bad ) return 'e'; // 在同一直线上且一定有交点(第一步已判显性分离)
		else if( !bac ) p = c;
		else if( !bad ) p = d;
		else if( !dca ) p = a;
		else if( !dcb ) p = b;
		else assert(0);
		return 'v'; // 端点相交
	}
}

typedef pair<int,int> pii;
template<class T> void inline checkMax(T& a, T b){if(a < b) a = b;};
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)
#define two(x) (1<<(x))
const int MAXN = two(17); // 128 * 1024
pii max_value[MAXN*2];
int C[MAXN*2];
int M = 1;
void add(int a, int b, int c){
	a+=M; b+=M;
	//           [1]
	//     [2]         [3]
	//  [4]   [5]   [6]   [7]
	// [] [] [] [] [] [] [] [] 
	bool meet = false;
	for(; a || b ; a/=2, b/=2){
		if( a / 2 != b / 2 ){ // 懒标记
			if( (a ^ 1) < a )C[a^1] -= c;
			if( b < (b ^ 1) )C[b^1] -= c;
		}
		if( a == b ){ // 跳出
			if(!meet)C[a] += c;
			meet = true;
		}
#define newv(a) pii(max_value[a].first + C[a], max_value[a].second)
		max_value[a/2] = max( newv(a), newv(a^1) );
		max_value[b/2] = max( newv(b), newv(b^1) );
	}
}
pii get(int a, int b){
	a+=M; b+=M;
	pii maxa(max_value[a]), maxb(max_value[b]);
	for(;a || b ; a/=2, b/=2){
		maxa.first += C[a];
		maxb.first += C[b];
		if( a / 2 != b / 2 ){
			if( a < (a ^ 1) )checkMax( maxa, newv(a^1) );
			if( (b ^ 1) < b )checkMax( maxb, newv(b^1) );
		}
	}
	return max(maxa, maxb);
}

int n, K;
const int MAXN = 64*64*2;
const int MAXM = MAXN*8;
const int SIZE_QUEUE = 13;
int mat[64][64];
int w[MAXN];
int cost[MAXM]，cap[MAXM];
int nxt[MAXM], name[MAXM];
int st[MAXN];
int nedges;
int flow[MAXM];
int sp[MAXN], from[MAXN];
int oo = 0x7f7f7f7f;

//循环队列
struct CicleQueue{
	int _data[two(SIZE_QUEUE)];
	int& operator[](int a){
		return _data[a&two(SIZE_QUEUE)-1];
	}
};

CicleQueue Q;
bool spfa(int src, int dst, int n){
	bitset<MAXN> mk;
	mk.reset();
	memset(sp,0x3f,(sizeof sp));
	memset(from,-1,(sizeof from));
	
	mk[src] = true;
	sp[src] = 0;

	int qs = 0, qe = 1;
	Q[qs] = src;
	for(;qs != qe;){
		int cur = Q[qs++];
		for(int i = st[cur]; i != -1; i = nxt[i] )if( flow[i] ){
			int son = name[i];
			int better = sp[cur] + cost[i];
			if( better < sp[son] ){
				sp[son] = better;
				from[son] = i;
				if( !mk[ son ] ){
					mk[son] = true;
					Q[qe++] = son;
				}
			}
		}
		mk[cur] = false;
	}
        //判断是否找到了一条最短路
	return from[dst] != -1;
}

int min_cost_max_flow(int src, int dst, int n){
	int maxflow = 0, mincost = 0;
	for(;;){
		if( !spfa(src, dst, n)){
			return mincost ;
		}
		int aug = oo;
		for(int i = from[dst]; i != -1; i = from[name[i^1]] ){
			checkMin( aug, flow[i] );
		}
		if( !aug ) return mincost;

		maxflow += aug;
		mincost += sp[dst] * aug;
		for(int i = from[dst]; i != -1; i = from[name[i^1]] ){
			flow[i] -= aug;
			flow[i^1] += aug;
		}
	}
	return mincost;
}

void init_edge(){
	memset(nxt,-1,(sizeof nxt));
	memset(st,-1,(sizeof st));
	
	nedges = 0;
}
void add_edge(int a, int b, int w, int c){
	cap[nedges] = w;
	cost[nedges] = c;
	name[nedges] = b;
	nxt[nedges] = st[a];
	st[a] = nedges;
	nedges++;
}

void S() throws SyntacticException{
    if(lookahead.equals(new Token('('))){
        match(new Token('('));
        L();
        match(new Token(')'));
    } else if(lookahead.equals(new Token('a'))){
        match(newToken('a'));
    }
}

void L() throws SyntacticException{
    if(lookahead.equals(new Token('('))){
        match(new Token('('));
        L();
        match(new Token(')'));
    } else if(lookahead.equals(new Token('a'))){
        match(newToken('a'));
    }
    Lp();
}

void Lp() throws SyntacticException{
    if(lookahead.equals(new Token(','))){
        match(new Token(','));

        if(lookahead.equals(new Token('('))){
            match(new Token('('));
            L();
            match(new Token(')'));
        }else{
            match(new Token('a'));
        }
        match(Lp);
    }else{
        //good
    }
}

null

ll mul_mod(ll x, ll y, ll n){
	// V x -> ( x = a T + b, 0 <= a <= T, 0 <= b < T ) 
	x %= n;
	y %= n;
	ll T = floor( sqrt(n) + 0.5 );

	// |t| < T
	ll t = T * T - n;

	ll a = x / T; ll b = x % T;
	ll c = y / T; ll d = y % T;
	ll e = a * c / T; ll f = a * c % T;
	
	ll v = ( ( a * d + b * c ) % n + e * t ) % n;
	ll g = v/T; ll h = v % T;
	ll ans =(( (f+g) * t % n + b * d ) % n + h * T ) % n;
	while(ans<0)ans+=n;
	return ans;
}


ll pow_mod(ll a, ll n, ll p){
	ll d = a % p;
	ll ans = 1;
	for(; n; n>>=1){
		if(n&1) ans = mul_mod( ans, d, p );
		p = mul_mod( d, d, p );
	}
	return ans;
}

/***********************Time management***************************************/
#include <time.h>
#include <sys/time.h>
double gettime(){
	struct timeval t;
	gettimeofday(&t, NULL); 
	return t.tv_sec + t.tv_usec/1000000.0;
}
double startTime;
/******************************************************************************/

#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;
}

贴SGU 382 Cantor Functions 用做JAVA分数模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

import java.util.*;
import java.math.*;
import java.io.*;

class Fraction{
	BigInteger den, num;
	Fraction(){}
	Fraction(int a){
		den = BigInteger.ONE;
		num = BigInteger.valueOf(a);
	}
	Fraction(BigInteger a){
		den = BigInteger.ONE;
		num = a;
	}
	void simplify(){
		BigInteger gcd = den.gcd(num);
		den = den.divide(gcd);
		num = num.divide(gcd);
	}
	Fraction subtract( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).subtract( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction add( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.den ).add( b.num.multiply( den ) );
		c.simplify();
		return c;
	}
	Fraction multiply( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.den );
		c.num = num.multiply( b.num );
		c.simplify();
		return c;
	}
	Fraction divide( Fraction b){
		Fraction c = new Fraction();
		c.den = den.multiply( b.num );
		c.num = num.multiply( b.den );
		c.simplify();
		return c;
	}
	void print(){
		System.out.println( num + "/" + den );
	}
}


public class Solution{
	static public void main( String argv[] ) throws IOException{
		Scanner scanner = new Scanner( System.in );
		int n = scanner.nextInt();
		// calc Cnk 
		Fraction C[][] = new Fraction[n+1][n+1];
		for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) C[i][j] = new Fraction(0);
		for(int i = 0; i <= n; ++i) C[i][0] = new Fraction(1);
	
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j<= i; ++j){
				C[i][j] = C[i-1][j].add( C[i-1][j-1] );
			}
		}

		Fraction F[] = new Fraction[n+1];
		F[0] = new Fraction(1);
		BigInteger three = BigInteger.valueOf(3);
		BigInteger two = BigInteger.valueOf(2);
		for(int i = 1; i <= n; ++i){
			Fraction sum = new Fraction(1);
			Fraction div = new Fraction(BigInteger.ONE.shiftLeft(i).multiply(three).subtract(two) );
			for(int j = 0; j < i; ++j){
				sum = sum.add( F[j].multiply( C[i][j] ) );
			}
			F[i] = sum.divide(div);
		}
		F[n].print();
	}
}

#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)

const int MAXN = 212345;
char str[MAXN];
int sa[MAXN], rank[MAXN], work[MAXN], bkt[MAXN], perm[MAXN], height[MAXN];
inline bool cmp(const int& a, const int& b, const int& l){
	return rank[a] == rank[b] && rank[a+l] == rank[b+l];
}
void build_sa(int n, int bkt_sz = 128){
	Rep(i,n)work[i] = str[i];

	// bucket sort [ work -> sa ]
	fill( bkt, bkt + bkt_sz, 0 );
	Rep(i,n) bkt[ work[i] ]++;
	partial_sum( bkt, bkt + bkt_sz, bkt );
	for(int i = n-1; i>=0; --i) sa[ --bkt[work[i]] ] = i;
	// current rank
	copy( work, work + n, rank );

	for(int step = 1; ; step *= 2){
		int p = 0; for(int i = n-step; i < n; ++i) perm[p++] = i;
		Rep(i,n)if(sa[i] >= step) perm[p++] = sa[i] - step;
		assert( p == n );
		Rep(i,n)work[i] = rank[ perm[i] ];

		// bucket sort [ work -> sa ]
		fill( bkt, bkt + bkt_sz, 0 );
		Rep(i,n) bkt[ work[i] ]++;
		partial_sum( bkt, bkt + bkt_sz, bkt );
		for(int i = n-1; i>=0; --i) sa[ --bkt[work[i]] ] = perm[i]; // 这句和前面不一样

		bkt_sz = 0;
		work[sa[0]] = bkt_sz++;
		for(int i = 1; i < n; ++i) work[sa[i]] = cmp(sa[i], sa[i-1], step ) ? bkt_sz-1 : bkt_sz++;
		copy( work, work + n, rank );
		if( bkt_sz == n ) break;
	}

	int cur = 0;
	for(int i = 0; i < n-1; ++i){
		if( --cur < 0 ) cur = 0;
		while( str[i + cur] == str[ sa[rank[i]-1] + cur ] ) cur++;
		height[rank[i]] = cur;
	}
}

const int N = 1024;
struct Qua{
	int x, y, X, Y, len;
	char val;
	Qua *nxt[4];
};
void build(int x, int y, int X, int Y, Qua* cur){
	cur->x = x; 
	cur->y = y; 
	cur->X = X; 
	cur->Y = Y; 
	if( X-x == 1 && Y - y == 1){
		cur->val = -1;
		cur->x = x; cur->y = y; cur->X = X; cur->Y = Y;
		return;
	}
	if( X-x < 1 ) return;
	if( Y-y < 1 ) return;
	int mx = (x+X)/2, my = (y+Y)/2;
	build(x,y,mx,my, cur->nxt[0] = new Qua);
	build(mx,my,X,Y, cur->nxt[1] = new Qua);
	build(mx,y,X,my, cur->nxt[2] = new Qua);
	build(x,my,mx,Y, cur->nxt[3] = new Qua);
}


void update(int x, int y, int X, int Y, Qua* cur, char color){
	if( X <= cur->x || cur->X <= x ||
	    Y <= cur->y || cur->Y <= y ) return;
	x = max(x,cur->x);
	X = min(X,cur->X);
	y = max(y,cur->y);
	Y = min(Y,cur->Y);
	if( x == cur->x && X == cur->X && y == cur->y && Y == cur->Y ){
		cur->val = color;
		return;
	}
	if( cur->val != -1 )Rep(i,4)cur->nxt[i]->val = cur->val;
	cur->val = -1; // 清除懒惰标志，不能忘记
	Rep(i,4)update(x,y,X,Y,cur->nxt[i],color);
}


int get(Qua* cur){
	if( cur->val != -1 )return cur->val == 'w' ? (cur->Y-cur->y)*(cur->X-cur->x) : 0;
	int ans = 0;
	Rep(i,4)ans += get(cur->nxt[i]);
	return ans;
}