Codeforeces Educational Codeforces Round 109(A-D)部分

A. Potion-making

大概就是要问你要多少步，可以构造出来一个百分数. 比如构造出25%，那么就是1/(3+1),答案是4. 构造3%，就是3/(97+3) 答案是100. 很显然，答案是一个这样的形式 n/m.而且这个形式n和m不能互相约分，那么m就是这个答案，使用一下gcd进行约分即可.

#include
using namespace std;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		int ans=100/gcd(100,n);
		coutm;
		vector a(n);
		for(int i=0;ich;
			if(ch=='L') a[i].dr=0;
			else a[i].dr=1;
		}
		sort(a.begin(),a.end());
		vector ans(n,-1);
		vector s(2);
		for(auto i : a){
			int k=i.x%2;
			if(i.dr){  // if i is the right direction, push it in the stack
				s[k].push_back(i);
			}
			else {          // if i is the left direction check the stack.
			if(!s[k].empty()){ // if the stack isn't empty ,calculate the ans
			   Node l = s[k].back();
			   s[k].pop_back();
			   int id1=l.id,id2=i.id;
			   if(l.dr) {   //the x1 is right direction
			   	ans[id1]=ans[id2]=(i.x-l.x)/2;
			   }
			   else ans[id1]=ans[id2]=(i.x+l.x)/2;      
			}
			else s[k].push_back(i);
		}
	}
	for(int i=0;i1){
			Node r=s[i].back();s[i].pop_back();
			Node l=s[i].back();s[i].pop_back();
			if(l.dr){ //if x1 is right direction
				ans[l.id]=ans[r.id]=m-(l.x+r.x)/2;
			}
			else {
				ans[l.id]=ans[r.id]=m+(l.x-r.x)/2;
			}
		}
	}
	for(auto i : ans){
		printf("%d ",i);
	}
	coutt的边，费用为0，容量为1. 接下来是重点.每个相邻的两个点之间，都建立一条边（实际上是无向边）.容量为INF（代表可以任意转换）,费用为1. 这样问题就变成求解s,t的一个费用流 套用板子即可.
 
#include
using namespace std;
const int maxn = 5005;
const int INF = 1e9+7;
int ans=0;
struct Edge{
	int from,to,cap,flow,cost;
};
struct Node{
	int v,cost;
	bool operator rhs.cost;
	}
};
struct MCMF{
	int n,m,s,t;    
	vector edges;vector G[maxn];
	int vis[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i>n;
	vector v1;
	vector v2;
	int s=0,t=n+1;
	g.init(n+3);
	for(int i=1;i0) v1.push_back(i);
		else v2.push_back(i);
	}
	for(auto i : v1){
		g.addedge(0,i,1,0);
	}
	for(int i=1;i