D1图论最短路专题

第一题:poj3660

其实是Floyed算法的拓展:Floyd-Wareshall。初始时,若两头牛关系确定则fij = 1。 对于一头牛若确定的关系=n-1,这说明这头牛的排名是确定的。

通过寻找节点k来判断;

#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
inline int read()
{
int x=,f=;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='- ') f=-;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
int n,m,x,y,f[][],ans,tot;
void floyed()
{
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
f[i][j]=f[i][j]|f[i][k]&f[k][j];
}
int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
x=read();y=read();
f[x][y]=;
}
floyed();
for(int i=;i<=n;i++)
{
int ans=;
for(int j=;j<=n;j++)
{
if(f[i][j]||f[j][i]) ++ans;
}
if(ans==n-) ++tot;
}cout<<tot;
return ;
}

第二题:UVA11374枚举(还没写,会补上);

第三题:bzoj4152 考虑建边,如果暴力建边则需要建n2条边,显然不可接受。

可以分析一下边权的性质:对于(x1, y1),(x2, y2),(x3, y3)这三个点 若x1 ≤ x2 ≤ x3,(即相邻)则从x方向由P1− > P3的边可以 由(P1− > P2) + (P2− > P3)组成,所以P1− > P3的边可以不用显式的 建出来,而是由P1− > P2 和P2− > P3 的边构成。 注意:本题最短路算法卡SPFA。(我写过一篇这个题解,https://www.cnblogs.com/Tyouchie/p/10360824.html可参考)

#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#define inf 0x3f
using namespace std;
#define pii pair<int,int>
inline int read()
{
int x=,f=;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
struct pink
{
int x,y,id;
}h[];
struct gg
{
int y,next,v;
}a[<<];
bool mycmp1(pink a,pink b)
{
return a.x<b.x;
}
bool mycmp2(pink s,pink m)
{
return s.y<m.y;
}
int lin[],n,m,tot;
bool vis[];
long long dis[];
inline void init(int x,int y,int z)
{
a[++tot].y=y;
a[tot].v=z;
a[tot].next=lin[x];
lin[x]=tot;
}
/*void dijkstra(int s)
{
priority_queue<pii,vector<pii>,greater<pii> >q;
for(int i=1;i<=n;i++)
dis[i]=inf*(i!=s);
q.push(pii(dis[s],s));
while(!q.empty())
{
pii now=q.top();q.pop();
int u=now.second;
// cout<<")"<<u<<endl;system("pause");
if(dis[u]<now.first) continue;
for(int i=lin[u];i;i=a[i].next)
{
int v=a[i].y;
if(dis[v]>dis[u]+a[i].v)
{
dis[v]=dis[u]+a[i].v;
q.push(pii(dis[v],v));
}
}
}
}*/
inline void dijkstra_heap(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
priority_queue<pii,vector<pii>,greater<pii> >q;
dis[s]=;
q.push(make_pair(,s));
while (!q.empty())
{
int x=q.top().second;
q.pop();
if (vis[x]) continue;
vis[x]=;
for (int i=lin[x];i;i=a[i].next)
{
int y=a[i].y;
if (dis[y]>dis[x]+a[i].v)
{
dis[y]=dis[x]+a[i].v;
q.push(make_pair(dis[y],y));
}
}
}
}
int main()
{
n=read();
for(int i=;i<=n;i++)
h[i].id=i,h[i].x=read(),h[i].y=read();
sort(h+,h+n+,mycmp1);
for(int i=;i<n;i++)
init(h[i].id,h[i+].id,abs(h[i].x-h[i+].x)),init(h[i+].id,h[i].id,abs(h[i].x-h[i+].x));
sort(h+,h+n+,mycmp2);
for(int i=;i<n;i++)
init(h[i].id,h[i+].id,abs(h[i].y-h[i+].y)),init(h[i+].id,h[i].id,abs(h[i].y-h[i+].y));
dijkstra_heap();
cout<<dis[n]<<endl;
return ;
}

第四题:UVA10603 不会写对不起;

第五题:HYSBZ2662;主要是运用一个分层图的思想,注意到k是比较小的,所以我们可以把k强行拆开,把一个点分为k个,分别表示用k张卡片所走的最短路,我们可以理解为走了k个图,相邻图之间的路变为原来所走的路的一半,所以这样建图:各层内部正常连边,各层之间权值为一半的边。每跑一层,就相当于使用一次卡片。跑一遍从s到t+n*k的最短路即可,第i层和第i+1层之间路权值变为原来的一半;相当于用了一次卡,这里我用了dijkstra的堆优化(多练习一下刚学会),spfa也可以过;

#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
int h,n,m,k,s,t,a,b,c,tot,lin[];
inline int read()
{
int x=,f=;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
struct edge
{
int y,v,next;
}an[];
int dis[];
bool vis[];
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
void add(int x,int y,int z)
{
an[++tot].y=y;
an[tot].v=z;
an[tot].next=lin[x];
lin[x]=tot;
}
void diskstra_heap(int s)
{
memset(dis,,sizeof(dis));
dis[s]=;
q.push(make_pair(dis[s],s));
int x,j;
while (q.size())
{
x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=true;
for (int i=lin[x];i;i=an[i].next)
{
j=an[i].y;
if(dis[x]+an[i].v>=dis[j]) continue;
dis[j]=dis[x]+an[i].v;
q.push(make_pair(dis[j],j));
}
}
} int main()
{
n=read();m=read();k=read();
for (int i=;i<=m;++i)
{
a=read();b=read();c=read();
add(a,b,c);
add(b,a,c);
for (int j=;j<=k;++j)
{
add(j*n+a,j*n+b,c);
add(j*n+b,j*n+a,c);
add((j-)*n+a,j*n+b,c/);
add((j-)*n+b,j*n+a,c/);
}
}
s=,t=n;//从1到n的路径
diskstra_heap(s);
int ans=dis[t];
for(int i=;i<=k;++i)
ans=min(ans,dis[i*n+t]);
cout<<ans;
return ;
}

第六题:数论建图:luoguP2371;(重点强调神仙题)

这个题拿到题面,数学题?推结论 ?后来发现很明显不能写,如果直接寻找x的结果,可想。。。不可做;

后来学长一句话:无限背包跑最短路。wow什么,没听说过;

上课ppt的题解:题目可以理解成经典的背包问题。只是他问你的是[Bmin, Bmax ]区间 中有多少个容积是恰好可以装满的。范围很大,传统的暴力是行不通 的。 首先取出最小的ai,设为p。那么考虑令d[i]表示当物体的总 重mod p = i时,物体最少的重量。设d[i] = t,那么显然对于所有的x, 如果x mod p = i且t ≤ x,都可以用总重最少的那个方案再加上若干个p 到。 同时,考虑加入一个物体u,那么显然有d[(i + u) mod p]可以 由d[i] + u得到,这不就是两点间连边吗?d[i]求最小值不就是最短路 吗? 方案数转化为了最短路问题。(理解了好久觉得挺对)

另外:我们可以用数论的思想来转向图论思考;我们在这些数列an里任取一个ai,表示为k,那 么这个B%k肯定是在0–k-1之间的,如果一个B满足条件,B%k=d, 那么(B+k)%k也肯定为d,那其实就是说,只要我们能找到,B%k=d的, 且满足条件的最小的B,在一直往上加k,直到加到最大上届为止,并统计个数,(这些B都是符合条件的), 就得到了B%k=d所有的可能,在枚举不同的d,累加起来;

我们要d尽可能的小,就要k尽可能的小,所以我们对数列进行排序,取最小的ai,那么当前我们能寻找到最小的B;(有些题解说是同余最短路);

#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
inline long long read()
{
long long x=,f=;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='- ') f=-;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
long long dis[],vis[],tot,n,l,r;
long long mina,minb,minv=inf,a[];
void spfa()
{
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
queue<int>q;
dis[]=;vis[]=;
q.push();
while(q.size())
{
int x=q.front();q.pop();vis[x]=;
for(int i=;i<=n;i++)
{
int y=(x+a[i])%minv;
if(dis[y]>dis[x]+a[i])
{
dis[y]=dis[x]+a[i];
if(!vis[y]) vis[y]=,q.push(y);
}
}
}
}
long long query(long long x)
{
long long ans=;
for(int i=;i<minv;i++)
{
if(dis[i]<=x)
ans+=(x-dis[i])/minv+;
}
return ans;
}
int main()
{
n=read();l=read();r=read();
for(int i=;i<=n;i++)
{
a[i]=read();
if(!a[i])i--,n--;
minv=min(minv,a[i]);
}
spfa();
cout<<query(r)-query(l-);
return ;
}
上一篇:如何解决python连接数据库编码问题(python传数据到mysql乱码)'ascii' codec can't encode _mysql_exceptions.OperationalError: (1366, "Incorrect string value:?


下一篇:【Android Demo】通过WebService获取今日天气情况