第一题：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 ;
}