一些图论的题目
BZOJ 3445 Roadblock
求出最短路，枚举每条边再跑一遍即可(科技为了我
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int head[105],cnt=1;
struct edge
{
int dis,to,nxt;
}edg[10005];
inline void add(int u,int v,int w)
{
edg[++cnt].to=v;
edg[cnt].dis=w;
edg[cnt].nxt=head[u];
head[u]=cnt;
edg[++cnt].to=u;
edg[cnt].dis=w;
edg[cnt].nxt=head[v];
head[v]=cnt;
}
ll diss[105];
bool vis[105];
int pre[105];
ll qwq;
ll ans;
inline void dij()
{
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
q.push(make_pair(0,1));
for(int i=1;i<=n;i++) diss[i]=99999999999;
diss[1]=0;
while(!q.empty())
{
int now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=head[now];i;i=edg[i].nxt)
{
int v=edg[i].to;
if(diss[now]+edg[i].dis<diss[v])
{
diss[v]=diss[now]+edg[i].dis;
q.push(make_pair(diss[v],v));
pre[v]=i;
}
}
}
qwq=diss[n];
}
inline void dijnew()
{
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
q.push(make_pair(0,1));
for(int i=1;i<=n;i++) diss[i]=99999999999,vis[i]=0;
diss[1]=0;
while(!q.empty())
{
int now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=head[now];i;i=edg[i].nxt)
{
int v=edg[i].to;
if(diss[now]+edg[i].dis<diss[v])
{
diss[v]=diss[now]+edg[i].dis;
q.push(make_pair(diss[v],v));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dij();
for(int i=1;i<=n;i++)
{
int t=pre[i];
edg[t].dis<<=1;edg[t^1].dis<<=1;
dijnew();
ans=max(ans,diss[n]);
edg[t].dis>>=1;edg[t^1].dis>>=1;
}
cout<<ans-qwq;
}
建一个分层图
原图在第一层
第一层向第二层连有向边
对于u-->v,从第一层的u点向第二层的v点连一条长度为0的边
优于更新有可能用不到k次
从上一层的点u到下一层的点u连一条长度为0的边，表示不用这次更新
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int head[210005],cnt;
struct edge
{
int dis,to,nxt;
}edg[4200005];
inline void add(int u,int v,int w)
{
edg[++cnt].to=v;
edg[cnt].dis=w;
edg[cnt].nxt=head[u];
head[u]=cnt;
}
ll diss[210005];
bool vis[210005];
ll ans;
inline void dij()
{
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
q.push(make_pair(0,1));
for(int i=1;i<=n*(k+1);i++) diss[i]=9999999999;
diss[1]=0;
while(!q.empty())
{
int now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=head[now];i;i=edg[i].nxt)
{
int v=edg[i].to;
if(diss[now]+edg[i].dis<diss[v])
{
diss[v]=diss[now]+edg[i].dis;
q.push(make_pair(diss[v],v));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
for(int j=1;j<=k;j++)
{
add(j*n+u,j*n+v,w);
add(j*n+v,j*n+u,w);
add((j-1)*n+u,j*n+v,0);
add((j-1)*n+v,j*n+u,0);
}
}
dij();
ll ans=diss[n];
for(int i=1;i<=k;i++)
{
ans=min(ll(ans),diss[i*n+n]);
}
cout<<ans;
}
min(x3-x1,y3-y1)=x3-x1>=min(x2-x1,y2-y1)+min(x3-x2,y3-y2)
按x轴排序，相邻的点建边，然后建O(n)条
跑dij就行了
最小边越大，最大边越大
最小边变大之后，最大边能选取的范围变小了，且有可能会变大
固定最小边，最小化最大边
并查集维护连通性
先把最小边拿出来，看看能不能加进去，重复操作，直到s和t联通
把最小边从大往小枚举
每次新的边可用的时候，如果连通块正好联通就可以
如果会出环，那么找到u和v之前的路径上最大的边
对于枚举的最小边，看看最大边是谁
1.二分答案
所有长度<=mid的边属于部落内部
>mid的边属于部落外部
看看有多少个连通块
如果连通块数比k多就可行
2.kruscal
n^2连边
把部落看成连通块
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int fa[1005];
int cnt;
double ans;
struct edge
{
int from,to;
double dis;
}edg[1000005];
struct node
{
int x,y;
}nod[1005];
inline bool cmp(edge a,edge b)
{
return a.dis<b.dis;
}
inline int find(int x)
{
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
/*inline void kruscal()
{
int t=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=cnt;i++)
{
if(t==n-k)
{
ans=edg[i+1].dis;
return;
}
if(find(edg[i].to)!=find(edg[i].from))
{
fa[find(edg[i].to)]=find(edg[i].from);
t++;
}
}
}*/
inline void kruscal()
{
int t=0;
bool flag=0;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=cnt;i++)
{
if(t==n-k)
{
flag=1;
}
if(find(edg[i].to)!=find(edg[i].from))
{
fa[find(edg[i].to)]=find(edg[i].from);
t++;
if(flag==1)
{
ans=edg[i].dis;
return ;
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&nod[i].x,&nod[i].y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
edg[++cnt].from=i;
edg[cnt].to=j;
edg[cnt].dis=sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
}
}
sort(edg+1,edg+1+cnt,cmp);
kruscal();
printf("%.2lf",ans);
}
选一条边表示两个点属于同一个连通块
目标就是选若干条边使得图分成k个连通块，并且没有选中的边的最小值尽可能大
kruscal选中n-k条边就停止
知道了一个点的奇偶性就可以看出来它有没有
1,1~2,1~3,...,1~n的奇偶性就可以知道所有的奇偶性
前缀和任何一个可行的方案一定可以推出s1~sn
如果我询问了l~r，则我可以知道s[r]-s[l-1]的奇偶性
%2意义下加法就是异或
有传递性
如果我知道s[x]和s[y]奇偶相同，s[y]和s[z]奇偶相同，则s[x]和s[z]奇偶相同
已经知道s[0]=0
目的就是s[1]~s[n]的所有点和s[0]联通起来
有n^2条边，n+1个点，跑最小生成树就行了
贪心策略：在每一个点去往最近的加油站
以所有加油站为源点跑多源最短路，顺便维护最初的源点，现在知道每一个加油站离他最近的源点
可以看成在加油站之间的移动
枚举原图的边，如果两点最近加油站不同，就连边
对加油站跑最小生成树
留下最短路图的公共部分
留下有向边
一定无环（DAG）
求dag上最长路，拓扑+dp
设a1是最小的，在模a1意义下一个数的所有取值只有0~a1-1
而如果 k 是可被表示的，那么 k + a[1], k + 2 × a[1], . . . 都可被表示。故问题转化为求解每个位置最小可被表示数字。建a1个点
x-->(x+aj)%ai（相当于每次+aj）
就可以转移模数
希望走的边的长度尽可能小
大于这个东西就可以表示
加边之后从零点跑单源最短路
线形基
给你若干个int，把他们抑或起来，最后异或出来的数是有限的
发现原来的数是很冗余的，只需要其中某些数就可以达到原来的效果
1 xor 2 = 3 1,2,3是线性相关的 或者说 1 xor 2 xor 3 = 0
就是说保留两个就可以出来第三个
线性基是拟阵
遗传性，交换性
每一个数分配权值
给你一个集合
找到一个子集使得它的权值最小并且是线性基
怎么解释生成森林和线性基对应
每一条边对应二进制
当且仅当环异或起来是0
k条边最短路
具有结合律
可以求出A^1,A^2,A^4...
也可以快速幂
O(n^3logn)
应用：
给你一张图，判断最小的负环
求A^1,A^2,A^3...有没有负环，如果有的话就是最小的
可以二分优化
用倍增的思想往上跳