[ Fraction ] 分數模板

今天學弟的比賽剛結束，因為有考到相關內容所以到現在才釋出分數模板。
因為每種題目要求輸出的分數格式都不一樣，所以不提供輸出的程式，必定約到最簡分數。
以下提供模板:

	/************************
	n為分子，d為分母
	若分數為0則n=0,d=1
	若為負數則負號加在分子
	必定約到最簡分數
	************************/
	#ifndef SUNMOON_FRACTION
	#define SUNMOON_FRACTION
	#include<algorithm>
	template<typename T>
	struct fraction{
	T n,d;
	fraction(const T &_n=0,const T &_d=1):n(_n),d(_d){
	T t=std::__gcd(n,d);
	n/=t,d/=t;
	if(d<0)n=-n,d=-d;
	}
	fraction operator-()const{
	return fraction(-n,d);
	}
	fraction operator+(const fraction &b)const{
	return fraction(n*b.d+b.n*d,d*b.d);
	}
	fraction operator-(const fraction &b)const{
	return fraction(n*b.d-b.n*d,d*b.d);
	}
	fraction operator*(const fraction &b)const{
	return fraction(n*b.n,d*b.d);
	}
	fraction operator/(const fraction &b)const{
	return fraction(n*b.d,d*b.n);
	}
	fraction operator+=(const fraction &b){
	return *this=fraction(n*b.d+b.n*d,d*b.d);
	}
	fraction operator-=(const fraction &b){
	return *this=fraction(n*b.d-b.n*d,d*b.d);
	}
	fraction operator*=(const fraction &b){
	return *this=fraction(n*b.n,d*b.d);
	}
	fraction operator/=(const fraction &b){
	return *this=fraction(n*b.d,d*b.n);
	}
	bool operator <(const fraction &b)const{
	return n*b.d<b.n*d;
	}
	bool operator >(const fraction &b)const{
	return n*b.d>b.n*d;
	}
	bool operator ==(const fraction &b)const{
	return n*b.d==b.n*d;
	}
	bool operator <=(const fraction &b)const{
	return n*b.d<=b.n*d;
	}
	bool operator >=(const fraction &b)const{
	return n*b.d>=b.n*d;
	}
	};
	#endif

view raw fraction.cpp hosted with ❤ by GitHub

[ shortest path algorithm ] floyd,dijkstra,bellman,spfa 最短路徑模板

Floyd-Warshall:

	int n;
	int d[105][105];
	int g[105][105];
	/*************************
	點數
	答案
	圖，如果兩點間不存在邊則為INF
	*************************/
	inline void floyd(){
	static int i,j,k;
	for(i=0;i<n;++i){
	for(j=0;j<n;++j){
	d[i][j]=g[i][j];
	}
	}
	for(k=0;k<n;++k){
	for(i=0;i<n;++i){
	for(j=0;j<n;++j){
	if(d[i][j]>d[i][k]+d[k][j]){
	d[i][j]=d[i][k]+d[k][j];
	}
	}
	}
	}
	}

view raw Floyd-Warshall.cpp hosted with ❤ by GitHub

Dijkstra:

	const int MAXN=50005;
	const long long INF=0x3f3f3f3f3f3f3f3f;
	typedef pair<long long ,int > PLI;
	typedef pair<int ,long long > PIL;
	int n,m;//點數、邊數
	vector<PIL> g[MAXN];//圖
	long long d[MAXN];//答案
	inline bool dijkstra(int from,int to){
	priority_queue<PLI,vector<PLI>,greater<PLI> >q;
	for(int i=1;i<=n;++i)d[i]=INF;
	d[from]=0;
	q.push(make_pair(d[from],from));
	while(q.size()){
	PLI u=q.top();
	q.pop();
	int x=u.second;
	if(d[x]<u.first)continue;
	for(size_t i=0;i<g[x].size();++i){
	if(d[g[x][i].first]>d[x]+g[x][i].second){
	d[g[x][i].first]=d[x]+g[x][i].second;
	q.push(make_pair(d[g[x][i].first],g[x][i].first));
	}
	}
	}
	return d[to]==INF?0:1;//有/無解
	}

view raw Dijkstra.cpp hosted with ❤ by GitHub

Bellman-Ford:

	#define x first
	#define y second
	const long long INF=0x3f3f3f3f3f3f3f3f;
	const int MAXN=1005,MAXM=100005;
	int n,m;//點、邊的個數
	pair<pair<int,int > ,int > e[MAXM];//所有邊
	long long d[MAXN];//答案
	int bellman(int from,int to){
	for(int i=0;i<n;++i)d[i]=INF;
	d[from]=0;
	for(int t=1;t<=n;++t){
	bool fix=0;
	for(int i=0;i<m;++i){
	if(d[e[i].x.x]!=INF&&d[e[i].x.y]>d[e[i].x.x]+e[i].y){
	if(e[i].x.y==to&&t==n)return -1;//從from到to會經過負環
	d[e[i].x.y]=d[e[i].x.x]+e[i].y;
	fix=1;
	}
	}
	if(!fix)break;
	}
	return d[to]!=INF;//有/無解
	}

view raw Bellman-Ford.cpp hosted with ❤ by GitHub

SPFA:

	const int MAXN=50005;
	const long long INF=0x3f3f3f3f3f3f3f3f;
	typedef pair<int,long long > PIL;
	int n,m;//點數、邊數
	vector<PIL> g[MAXN];//圖
	long long d[MAXN];//答案
	bool inq[MAXN];//是否在queue裡面
	int inq_cnt[MAXN];//進queue的次數
	inline int spfa(int from,int to){
	queue<int > q;
	for(int i=1;i<=n;++i)d[i]=INF,inq[i]=inq_cnt[i]=0;
	d[from]=0;
	inq[from]=inq_cnt[from]=1;
	q.push(from);
	while(q.size()){
	int o=q.front();
	q.pop();
	if(inq_cnt[o]>n)return -1;//存在負環
	inq[o]=0;
	for(size_t i=0;i<g[o].size();++i){
	if(d[g[o][i].first]>d[o]+g[o][i].second){
	d[g[o][i].first]=d[o]+g[o][i].second;
	if(!inq[g[o][i].first]){
	inq[g[o][i].first]=1;
	++inq_cnt[g[o][i].first];
	q.push(g[o][i].first);
	}
	}
	}
	}
	return d[to]!=INF;//有/無解
	}

view raw SPFA.cpp hosted with ❤ by GitHub

[ Ternary Search ] 三分搜尋法模板

對於一個U型或倒U型函數，我們可以利用三分搜尋法找出其最低/最高點，時間複雜度為$\ord{log \; n}$,這裡n是$10^{(整數位數+浮點位數)}$

關於原理就不多說了，以下提供對於U型函數的模板:

	/*
	f是傳入的函數，eps表示精準度，通常設為1e-5
	l,r為邊界，所以必須先預估出極值點的位置
	*/
	template<typename _F>
	inline double ternary_search(_F f,double l,double r,double eps){
	static double m1,m2;
	while(r-l>eps){
	m1=l+(r-l)/3;
	m2=r-(r-l)/3;
	if(f(m1)>f(m2))l=m1;/*如果對象是倒U型函數，則改成 < */
	else r=m2;
	}
	return (l+r)/2;
	}

view raw ternary_search.cpp hosted with ❤ by GitHub

用法:

	inline double f(double x){
	return x*x-2*x+1;
	}
	/*假設邊界為-10~10*/
	printf("%.5f\n",ternary_search(f,-10,10,1e-6));

view raw use_way.cpp hosted with ❤ by GitHub