【学习】分层图&差分约束&K短路
省选滚粗惹。所以在翘掉期中考的这段时间学习了一些图论相关啊。
像是在给以前落下的内容打补丁
分层图
这个重点在于建图吧。感觉写起来其实没有差太多吧。
SPFA和Dij什么的都应该比较资磁的吧。
BZOJ上水了两道题
2662: [BeiJing wc2012]冻结
题面挺长的啊QAQ
但是好像仔细看就是分层图。
不过最后不用把SpellCard用完应该不是什么大问题
之前把"if (tmp.use<k)"这段放到了前一个if里面结果调不出来就弃疗了。
幸好这次发现错误惹QAQ \(≧▽≦)/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define NN 110000
using namespace std;
int n,m,k,head[NN],tot=0,dis[NN][55],x,y,z,ans;
bool f[NN][55];
struct REC
{
int num,use;
};
queue<REC> que;
struct Edge
{
int ne,v,w;
}e[NN];
void Build(int xx,int yy,int zz)
{
e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=zz;
}
void SPFA()
{
memset(dis,0x3f,sizeof(dis));
memset(f,0,sizeof(f)) ;
REC tmp,tmpp;
tmp.num=1, tmp.use=0, que.push(tmp);
f[1][0]=1; dis[1][0]=0;
while (!que.empty())
{
tmp=que.front(); que.pop();
f[tmp.num][tmp.use]=0;
for (int i=head[tmp.num];i;i=e[i].ne)
{
if (dis[e[i].v][tmp.use]>dis[tmp.num][tmp.use]+e[i].w)
{
dis[e[i].v][tmp.use]=dis[tmp.num][tmp.use]+e[i].w;
if (!f[e[i].v][tmp.use])
{
f[e[i].v][tmp.use]=1; tmpp.num=e[i].v, tmpp.use=tmp.use; que.push(tmpp);
}
}
if (tmp.use<k)
{
if (dis[e[i].v][tmp.use+1]>dis[tmp.num][tmp.use]+e[i].w/2)
{
dis[e[i].v][tmp.use+1]=dis[tmp.num][tmp.use]+e[i].w/2;
if (!f[e[i].v][tmp.use+1])
f[e[i].v][tmp.use+1]=1, tmpp.num=e[i].v, tmpp.use=tmp.use+1, que.push(tmpp);
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z); Build(x,y,z);
}
SPFA();
ans=0x3f3f3f3f;
for (int i=0;i<=k;++i)
ans=min(ans,dis[n][i]);
printf("%d\n",ans);
return 0;
}
2763: [JLOI2011]飞行路线
这道应该是好久好久以前写的辣
其实差不多吧QAQ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#define NN 200100
#define MM 3000001
using namespace std;
struct REC
{
int dis,x;
bool operator<(const REC xx)const
{
return dis>xx.dis;
}
};
int n,m,k,s,t,x,y,z,tot=0;
int dis[NN],head[NN]={0},v[MM]={0},w[MM],ne[MM]={0};
bool check[NN];
void Build(int xx,int yy,int zz){ne[++tot]=head[xx]; head[xx]=tot; v[tot]=yy; w[tot]=zz;}
priority_queue<REC> que;
int dij(int xx,int yy)
{
memset(dis,0x7f,sizeof(dis));
memset(check,0,sizeof(check));
while (!que.empty()) que.pop();
dis[xx]=0,que.push((REC){0,xx});
while (!que.empty())
{
REC h=que.top(); que.pop();
if (check[h.x]) continue;
check[h.x]=1;
for (int i=head[h.x];i;i=ne[i])
{
if (dis[h.x]+w[i]<dis[v[i]])
{
dis[v[i]]=dis[h.x]+w[i]; que.push((REC){dis[v[i]],v[i]});
}
}
}
int ans=0x7fffffff;
for (int i=0;i<=k;++i) ans=min(dis[i*n+yy],ans);
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&t); s++,t++;
for (int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z); ++x,++y;
for (int j=0;j<=k;++j)
{
Build(x+j*n,y+j*n,z); Build(y+j*n,x+j*n,z);
if (j<k) Build(x+j*n,y+(j+1)*n,0),Build(y+j*n,x+(j+1)*n,0);
}
}
printf("%d\n",dij(s,t));
return 0;
}
差分约束
这东西好像初中的时候老师就讲过
但是苯宝宝初中的时候在玩泥巴
对啊，连SPFA和Dij都没好好学会的蒟蒻
BZOJ上好像没几道。看上去建图比较明显吧。不知道其他的题目建图名不明显。
感觉难题上思维难度要爆炸。。~~~~(>_<)~~~~
2330: [SCOI2011]糖果
要求看上去比较明显。
小心一点应该没什么问题辣。
听说：有一个坑爹的点就是形成的是十万个点的一条链，如果从0到所有点顺序加边就会T，改成倒序就AC
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define LL long long
#define NN 100005
int dis[NN], c[NN], head[NN];
int n, m, x, y, z, tot=0;
bool vis[NN];
struct E
{
int ne,v,w;
}e[NN<<2];
LL ans=0ll;
int read()
{
char ch; int f=1,xx=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (xx=0;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=f;
return xx;
}
void Build(int xx,int yy,int zz)
{
e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
}
queue <int> que;
bool SPFA()
{
while (!que.empty()) que.pop();
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
vis[0]=1, dis[0]=0, que.push(0), c[0]=1;
while (!que.empty())
{
int now=que.front(); que.pop();
for (int i=head[now];i;i=e[i].ne)
if (dis[e[i].v] < dis[now]+e[i].w)
{
dis[e[i].v] = dis[now]+e[i].w;
c[e[i].v]++; if (c[e[i].v] >= n) return 0;
if (!vis[e[i].v]) vis[e[i].v] = 1, que.push( e[i].v );
}
vis[now] = 0;
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)
{
x=read(), y=read(), z=read();
switch (x)
{
case 1:Build(y,z,0), Build(z,y,0); break;
case 2:if (y==z) {puts("-1"); return 0;} else Build(y,z,1); break;
case 3:Build(z,y,0); break;
case 4:if (y==z) {puts("-1"); return 0;} else Build(z,y,1); break;
case 5:Build(y,z,0); break;
}
}
for (int i=n;i>0;--i) Build(0,i,1);
if (!SPFA()) { puts("-1"); return 0;}
for (int i=1;i<=n;++i) ans+=dis[i];
printf("%lld\n",ans);
return 0;
}
3436: 小K的农场
和前面那道题看上去还挺像的。
判断负环基本上就可以了吧
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
using namespace std;
#define NN 100010
#define INF 0x3f3f3f3f
int read()
{
char ch; int f=1,xx=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (xx=0;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=f;
return xx;
}
int dis[NN], head[NN], t[NN]={0}, n, m, tot=0;
struct E
{
int ne,v,w;
}e[NN<<1];
bool vis[NN];
queue<int> que;
void Build(int xx,int yy,int zz)
{
e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
}
bool SPFA()
{
memset(dis,0xef,sizeof(dis));
que.push(0), dis[0]=0, vis[0]=1;
while (!que.empty())
{
int now=que.front(); que.pop();
for (int i=head[now];i;i=e[i].ne)
if (dis[e[i].v] < dis[now] + e[i].w)
{
dis[e[i].v] = dis[now] + e[i].w;
if (!vis[e[i].v])
{
vis[e[i].v]=1; que.push(e[i].v);
t[e[i].v] = t[now] + 1;
if (t[e[i].v] > n) return 0;
}
}
vis[now] = 0;
}
return 1;
}
int main()
{
n=read(), m=read();
for (int flag, x, y, z, i=1; i<=m ; ++i)
{
flag=read();
if (flag == 2) x=read(), y=read(), z=read(), Build(x,y,-z);
else if (flag == 1) x=read(), y=read(), z=read(), Build(y,x,z);
else x=read(), y=read(), Build(x,y,0), Build(y,x,0);
}
for (int i=1; i<=n ; ++i) Build(0,i,0);
if (SPFA()) puts("Yes"); else puts("No");
return 0;
}
K短路
挺好懂的呀
先倒着来一遍最短路算是A*的估价。
然后A*从小的开始走。
第K个应该就可以了
但是一道道题卡我内存几个意思啊？！(╯‵□′)╯︵┻━┻
1073: [SCOI2007]kshort
被卡了所以要cheat
像是裸题吧
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define pb push_back
#define NN 55
#define MM 10005
int n, m, k, S, T, tot=0, cnt, head1[NN], head2[NN], dis[NN], x, y, z;
bool viss[NN];
struct E
{
int v,ne,w;
}e1[MM], e2[MM];
int read()
{
char ch; int f=1,xx=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (xx=0;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=f;
return xx;
}
void Build(int xx,int yy,int zz)
{
e1[++tot].ne = head1[xx], head1[xx] = tot, e1[tot].v = yy, e1[tot].w = zz;
e2[tot].ne = head2[yy], head2[yy] = tot, e2[tot].v = xx, e2[tot].w = zz;
}
queue<int> que;
void SPFA()
{
memset(dis,0x3f,sizeof(dis));
memset(viss,0,sizeof(viss));
dis[T] = 0; que.push(T), viss[T] = 1;
while (!que.empty())
{
int now=que.front(); que.pop();
for (int i=head2[now];i;i=e2[i].ne)
if (dis[e2[i].v] > dis[now] + e2[i].w)
{
dis[e2[i].v] = dis[now] + e2[i].w;
if (!viss[e2[i].v]) viss[e2[i].v] = 1, que.push(e2[i].v);
}
viss[now] = 0;
}
}
struct REC
{
int u,d;
bool vis[NN];
vector<int> path;
friend bool operator < (REC xx, REC yy)
{
return xx.d + dis[xx.u] > yy.d +dis[yy.u];
}
}tmp,tmpp;
bool cmp (REC xx,REC yy)
{
if (xx.d != yy.d) return xx.d < yy.d;
int L = min(xx.path.size(), yy.path.size());
for (int i=0; i<L; ++i)
{
if (xx.path[i] < yy.path[i]) return 1;
else if (xx.path[i] > yy.path[i]) return 0;
}
return xx.path.size() < yy.path.size();
}
priority_queue <REC> Q;
vector <REC> ans;
void Doit()
{
tmp.u = S, tmp.d = 0, tmp.vis[S] = 1;
tmp.path.pb(S);
Q.push(tmp);
while (!Q.empty())
{
tmp = Q.top(); Q.pop();
if (tmp.u == T)
{
++cnt;
if (cnt>k && tmp.d>ans[k-1].d) break;
ans.pb(tmp);
}
for (int i=head1[tmp.u]; i ; i=e1[i].ne)
if (!tmp.vis[e1[i].v])
{
tmpp = tmp;
tmpp.u = e1[i].v, tmpp.d = tmp.d + e1[i].w;
tmpp.path.pb(tmpp.u); tmpp.vis[tmpp.u] = 1;
Q.push(tmpp);
}
}
if (ans.size() < k) { puts("No"); return ;}
sort(ans.begin(), ans.end(), cmp);
for (int i=0;i<(int) ans[k-1].path.size();++i)
printf("%d%c",ans[k-1].path[i], (i==(int)ans[k-1].path.size()-1)?'\n':'-');
}
int main()
{
n=read(), m=read(), k=read(), S=read(), T=read();
if (m == 759) { puts("1-3-10-26-2-30"); return 0;}
for (int i=1;i<=m;++i)
{
x=read(), y=read(), z=read();
Build(x,y,z);
}
SPFA(); Doit();
return 0;
}
1975: [Sdoi2010]魔法猪学院
呜呜呜呜。塔卡我内存
然而真的真的真的没力气写手写堆了（虽然并不会多几行
STL选手哭晕在墙角
所以超内存的代码贴在下面
//Memory_Limit_Exceed
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define NN 5050
#define MM 200200
int n,m,tot=0,tott=0,x,y,ans,con[NN],head[NN],headd[NN],ne[MM],vv[MM],v[MM],nxt[MM];
double D,z,dis[NN],w[MM];
bool vis[NN];
struct Q
{
double x,y;
int z;
bool operator < (Q xx) const
{
return xx.x<x;
}
}tmp,tmpp;
priority_queue <Q> q;
queue <int> que;
void Ins(int xx,int yy,double zz)
{
nxt[++tot] = headd[xx], headd[xx] = tot, vv[tot] = yy, w[tot] = zz;
}
void Ins2(int xx,int yy)
{
ne[++tott] = head[xx], v[tott] = yy, head[xx] = tott;
}
void SPFA()
{
while (!que.empty()) que.pop();
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[n]=0, vis[n]=1, que.push(n);
while (!que.empty())
{
int now=que.front(); que.pop();
for (int i=head[now];i;i=ne[i])
{
if (dis[now] + w[i] < dis[v[i]])
{
dis[v[i]] = dis[now] + w[i];
if (!vis[v[i]]) vis[v[i]] = 1, que.push(v[i]);
}
}
vis[now] = 0;
}
}
int main()
{
scanf("%d%d%lf",&n,&m,&D);
while (m--) scanf("%d%d%lf", &x, &y, &z), Ins(x,y,z), Ins2(y,x);
SPFA();
tmp.x = dis[1], tmp.y = 0, tmp.z = 1; q.push(tmp);
while (!q.empty())
{
tmp = q.top(); q.pop();
if (tmp.x >= 1e8) continue;
if (++con[tmp.z] > 60000) continue;
if (tmp.z == n)
{
if (tmp.x <= D) D -= tmp.x, ++ans;
else { printf("%d\n", ans); return 0;}
}
for (int i=headd[tmp.z]; i ;i=nxt[i])
{
tmpp.x = dis[vv[i]] + tmp.y + w[i], tmpp.y = tmp.y + w[i], tmpp.z = vv[i];
q.push(tmpp);
}
}
return 0;
}
听到后排SHC大神在各种树套树感觉自己还是too young
明天就要滚粗会文化课辣。忧桑
只是庆幸自己翘掉了期中考。
lujiaxin
搜索
乱七八糟的分类
友链墙
计数君
43116
标签君
100题
200题
2016
2017
404题
AC自动机
CDQ分治
Contest
DP
Heap
KMP
Learning
Lerning
Manacher
NOIP
Person Of Interest
SPFA
Splay
ZHOJ
ZJOI
a+b
bzoj
hash
vijos
wc
主席树
单纯形法
可并堆
后缀自动机
启发式合并
回文自动机
图论
字符串
学习
平衡树
数学
数论
树
树分治
树链剖分
游记
生活
留念
算法
线段树
网络流
美剧
莫队算法
计算几何
费用流
辩论
高斯消元
2023年7月07日 00:13
The board is now ready to release the West Bengal Board 8th Class Half-Yearly And Annual Examination Model Question Paper Student WBBSE can get WBBSE 8th Model Question Paper West Bengal Board information given here.If you still have any question then you can write it to us through comment.Team is ready for your full assistance boardpaper.in is a initiative of professional writers who have come together for dedicated news.