luogup2526_[shoi2001]小狗散步_二分图匹配

关键词：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <math.h>
 5 #include <queue>
 6 using namespace std;
 7 #define N 600
 8 #define du double
 9 #define S (n+m+1)
10 #define T (n+m+2)
11 #define inf 100000000
12 int head[N],to[N*N<<1],nxt[N*N<<1],flow[N*N<<1],cnt=1,n,m,dep[N];
13 inline void add(int u,int v,int f){
14     to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;flow[cnt]=f;
15     to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;flow[cnt]=0;
16 }
17 struct P{
18     int x,y;
19 }a[N],b[N];
20 du dis(P u,P v){
21     return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
22 }
23 bool bfs(){
24     queue <int> q;
25     q.push(S);memset(dep,0,sizeof(dep));
26     dep[S]=1;
27     while(!q.empty()){
28         int x=q.front();q.pop();
29         for(int i=head[x];i;i=nxt[i]){
30             if(!dep[to[i]]&&flow[i]){
31                 dep[to[i]]=dep[x]+1;
32                 if(to[i]==T)return 1;
33                 q.push(to[i]);
34             }
35         }
36     }
37     return 0;
38 }
39 int dfs(int x,int mf){
40     if(x==T)return mf;
41     int nf=0;
42     for(int i=head[x];i;i=nxt[i]){
43         if(dep[to[i]]==dep[x]+1&&flow[i]){
44             int tmp=dfs(to[i],min(flow[i],mf-nf));
45             nf+=tmp;
46             flow[i]-=tmp;
47             flow[i^1]+=tmp;
48             if(nf==mf)break;    
49         }
50     }
51     dep[x]=0;return nf;
52 }
53 void dinic(){
54     int ans=0,f;
55     while(bfs())while(f=dfs(S,inf))ans+=f;
56     printf("%d
",ans+n);
57     for(int i=1;i<n;i++){
58         printf("%d %d ",a[i].x,a[i].y);
59         for(int j=head[i];j;j=nxt[j]){
60             if(to[j]!=S&&flow[j]==0){
61                 printf("%d %d ",b[to[j]-n+1].x,b[to[j]-n+1].y);    
62             }
63         }
64     }
65     printf("%d %d",a[n].x,a[n].y);
66 }
67 int main(){
68     scanf("%d%d",&n,&m);
69     for(int i=1;i<=n;i++){
70         scanf("%d%d",&a[i].x,&a[i].y);
71         if(i^n)add(S,i,1);
72     }
73     for(int i=1;i<=m;i++){
74         scanf("%d%d",&b[i].x,&b[i].y);    
75         add(i+n-1,T,1);
76     }
77     for(int i=1;i<n;i++){
78         for(int j=1;j<=m;j++){
79             if(dis(a[i],a[i+1])>=(dis(a[i],b[j])+dis(a[i+1],b[j]))/2){
80                 add(i,j+n-1,1);    
81             }
82         }
83     }
84     dinic();
85 }

[p2526][shoi2001]小狗散步(代码片段)

Link:P2526传送门Solution:一道提示非常到位的题目题面中强调了在两个路径相邻点间只能再去至多一个点，且每个点只计算一次贡献于是明显可以将原题看作询问在两个不相交点集间最多能连几条边接下来将合法边连上跑二分图匹... 查看详情

luogup4279[shoi2008]小约翰的游戏(代码片段)

LuoguP4279[SHOI2008]小约翰的游戏题目描述链接SolutionAnti-SG的模板题这里就直接放代码#include<bits/stdc++.h>usingnamespacestd;inlinelonglongread()longlongf=1,x=0;charch;doch=getchar();if(ch==‘-‘)f=-1;while(ch<‘0‘|| 查看详情

luogup1291[shoi2002]百事世界杯之旅

题目链接luoguP1291[SHOI2002]百事世界杯之旅题解设\(f[k]\)表示还有\(k\)个球员没有收集到的概率再买一瓶，买到的概率是\(k/n\)，买不到的概率是\((n-k)/k\)那么\(f[k]=f[k]*(n-k)/n+f[k-1]*k/n+1\)移向一下\(f[k]=f[k-1]+n/k\)代码#include<cstdio>#inclu... 查看详情

[luogup2912][usaco08oct]牧场散步pasturewalking（lca）

传送门 水题。直接倍增求lca。x到y的距离为dis[x]+dis[y]-2*dis[lca(x,y)] ——代码1#include<cstdio>2#include<cstring>3#include<iostream>4#defineMAXN2000256usingnamespacestd;78intn,q,cnt 查看详情

luogup3998[shoi2013]发微博

题目描述刚开通的SH微博共有n个用户（1Ln标号），在这短短一个月的时间内，用户们活动频繁，共有m条按时间顺序的记录：!x表示用户x发了一条微博；+xy表示用户x和用户y成为了好友?xy表示用户x和用户y解除了好友关系当一个用... 查看详情

[luogup2161[[shoi2009]会场预约(splay)(代码片段)

 题面传送门:https://www.luogu.org/problemnew/show/P2161    Solutionsplay的确有线段树/树状数组的做法,但我做的时候脑残没想到我们可以考虑写一个类似NOIP2017D2T3列队那道题那样的带分裂的平衡树考虑用splay维护每一条线... 查看详情

luogup3990[shoi2013]超级跳马(代码片段)

这道题还是一道比较不可做的矩阵题首先我们先YY一个递推的算法：令f[i][j]表示走到第i行第j列时的方案数，那么有以下转移：f[i][j]=f[i-1][j-2*k+1]+f[i+1][j-2*k+1]+f[i][j-2*k+1](1<=k<=i/2)但这样是很慢的，然后我们就可以前缀和优化这... 查看详情

排序工作量之新任务（shoi2001）

排序工作量之新任务（SHOI2001）给出两个整数n和t，求n的全排列中逆序对数为t的个数，和逆序对数为t的字典序最小全排列。首先第一个问题可以用dp解决，\(f[i][j]\)表示前i个数，j个逆序对的序列数，那么\(f[i][j]=f[i-1][j-k]\(k<i)(k... 查看详情

luogup3830[shoi2012]随机树期望概率+动态规划+结论(代码片段)

题意非常的复杂，考虑转化一下：每次选择一个叶节点，删除本叶节点（深度为$dep$）的同时，加入两个深度为$dep+1$的叶节点，重复$n$轮首先考虑第$1$问，（你看我这种人相信数据绝对是最大的数据，直接$f[i][S]$表示$i$个叶子结... 查看详情

搜索洛谷p2530[shoi2001]化工厂装箱员

P2530[SHOI2001]化工厂装箱员题目描述118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不... 查看详情

题解shoi2001化工厂装箱员

————传送：洛谷P2530这道题目还是挺简单的，状态也容易想到。数据范围非常的小，所以即便是很多维度，复杂度也完全可以接受。定义状态：dp[i][a][b][c]为手上的货物拿到第i个时三种物品分别有a,b,c个所用的最少次数。状... 查看详情

洛谷p2527[shoi2001]panda的烦恼

题目描述panda是个数学怪人，他非常喜欢研究跟别人相反的事情。最近他正在研究筛法，众所周知，对一个范围内的整数，经过筛法处理以后，剩下的全部都是质数，不过panda对这些不感兴趣，他只对被筛掉的数感兴趣，他... 查看详情

洛谷p2530[shoi2001]化工厂装箱员

题目描述118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱... 查看详情

p2530[shoi2001]化工厂装箱员(代码片段)

题目描述118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱... 查看详情

luogup2161[shoi2009]会场预约(代码片段)

题目地址题目链接题解用fhqtreap对区间进行维护。可以注意到的是，对于当前存在的预约，他们一定是升序排列的（有重叠的都被删了）。那么就可以用按照位置分裂的fhqtreap搞了（预约无论按l还是按r都必定是升序的）。每次插... 查看详情

bzoj4596/luogup4336[shoi2016]黑暗前的幻想乡(矩阵树定理，容斥)(代码片段)

bzoj4596/luoguP4336[SHOI2016]黑暗前的幻想乡(矩阵树定理，容斥)bzojLuogu题解时间看一看数据范围，求生成树个数毫无疑问直接上矩阵树定理。但是要求每条边都属于不同公司就很难直接实现。按套路上容斥：如果直接将几个公司的修... 查看详情

bzoj_1875_[sdoi2009]hh去散步_矩阵乘法

BZOJ_1875_[SDOI2009]HH去散步_矩阵乘法DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又... 查看详情

[luogup2224][hnoi2001]产品加工（背包dp）

传送门 f[i][j]表示第一个机器耗时j，第二个机器耗时f[i][j]第一维可以滚掉#include<cstdio>#include<cstring>#include<iostream>#defineINF1e9#definemin(x,y)((x)<(y)?(x):(y))#definemax(x,y)((x)>(y)?(x):(y)) 查看详情