【题目大意】给定一个无向图，求它的一棵生成树，使得权最大的边的权和最小的边的权差值最小。
【算法分析】枚举最短的一条边，然后对权值大于它的边进行Kruskal。直到构建好最小生成树，看目前最大边和枚举的那条边的权值之差是否小于ans
【其它】本来1A的，居然因为G++编译器问题CE了一遍
【code】
#include
[POJ 1679] 判断最小生成树是否唯一
【题目大意】求最小生成树是否唯一
【算法分析】使用prim算法，如果某一次加入的点是被几个已选点都更新过，且更新所得D值相等的话，必然导致多解。
【code】
#include
[URAL 1162] 判断正环
【题目大意】给定N个货币和M种兑换方式，问能否不断加钱？
【算法分析】用spfa算法判断有无正权回路。如果一个点进入队列超过N次。。。那就是有正权了。
【其它】注意精度要控制一下
【code】
#include
struct gtp{int x,y,next;double rate,sui;}g[201];
double d[101],sm;
int v[101],list[101],n,e,st,ls[101],insnum[101];
inline void addedge(int x,int y,double rate,double sui){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
g[e].rate=rate; g[e].sui=sui;
}
void init(){
int m; e=0;
scanf("%d%d%d%lf",&n,&m,&st,&sm);
for (int i=1;i<=m;i++){
double rate,sui;
int xx,yy;
scanf("%d%d%lf%lf",&xx,&yy,&rate,&sui);
addedge(xx,yy,rate,sui);
scanf("%lf%lf",&rate,&sui);
addedge(yy,xx,rate,sui);
}
}
bool spfa(){
memset(d,0,sizeof(d));
memset(v,0,sizeof(v));
memset(insnum,0,sizeof(insnum));
v[st]=1; d[st]=sm; insnum[st]=1; list[0]=st;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>100) head=0;
for (int t=ls[list[head]];t!=0;t=g[t].next)
if ((d[g[t].x]-g[t].sui)*g[t].rate>=d[g[t].y]+1e-6){
d[g[t].y]=(d[g[t].x]-g[t].sui)*g[t].rate;
if (v[g[t].y]==0){
v[g[t].y]=1;
tail++; if (tail>100) tail=0;
list[tail]=g[t].y;
insnum[g[t].y]++;
if (insnum[g[t].y]>n) return true;
}
}
v[list[head]]=0;
}
return false;
}
int main(){
init();
if (spfa()) printf("YESn");
else printf("NOn");
}
[POJ 3463] 最短路变形 求方案数
【题目大意】给定一个有向图，求从S走到F（最短路）和（最短路长度+1）的方案总和。
【算法分析】用dijkstra+heap求出最短路和次短路的方案和长度。如果最短路和次短路的长度相差1，那么将方案数相加，否则直接输出
【其它】1A
【程序】
#include
#define N 1111*2
#define INF 0x7FFFFFFF/2
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int ls[N],d[N],c[N],list[N],n,e,st,ed,zz[N];
struct headtpy{
int a[N],tot;
void up(int k){
while (k>1 && d[a[k]]
zz[a[k]]=k; zz[a[k/2]]=k/2;
k/=2;
}
}
void down(int k){
while (k*2<=tot){
int t=k*2;
if (t+1<=tot && d[a[t+1]]
swap(a[k],a[t]);
zz[a[k]]=k; zz[a[t]]=t;
k=t;
}
else break;
}
}
void ins(int locate){
tot++;
a[tot]=locate;
zz[locate]=tot;
up(tot);
}
void del(){
a[1]=a[tot];
tot–;
down(1);
}
}heap;
void init(){
scanf("%d%d",&n,&e);
memset(ls,0,sizeof(ls));
memset(zz,0,sizeof(zz));
for (int i=1;i<=e;i++){
int x,y,w;
scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].w);
g[i].next=ls[g[i].x]; ls[g[i].x]=i;
}
scanf("%d%d",&st,&ed);
for (int i=1;i<=2*n;i++){
d[i]=INF;
c[i]=0;
}
d[st*2-1]=0; c[st*2-1]=1;
heap.tot=0;
for (int i=1;i<=2*n;i++) heap.ins(i);
}
inline void push(int td,int tc,int ty){
if (td
c[ty*2]=c[ty*2-1];
heap.up(zz[ty*2]);
d[ty*2-1]=td;
c[ty*2-1]=tc;
heap.up(zz[ty*2-1]);
}
else if (td==d[ty*2-1]) c[ty*2-1]+=tc;
else if (td
c[ty*2]=tc;
heap.up(zz[ty*2]);
}
else if (td==d[ty*2]) c[ty*2]+=tc;
}
void dijkstra(){
while (heap.tot>0){
int p=(heap.a[1]+1)/2;
for (int t=ls[p];t!=0;t=g[t].next)
push(d[heap.a[1]]+g[t].w,c[heap.a[1]],g[t].y);
heap.del();
}
if (d[ed*2-1]+1==d[ed*2]) printf("%dn",c[ed*2-1]+c[ed*2]);
else printf("%dn",c[ed*2-1]);
}
int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int tc;
scanf("%d",&tc);
for (int i=1;i<=tc;i++){
init();
dijkstra();
}
}
[UVA10246] 巧妙优化 最短路 打表
看不到的请用firefox浏览器。
【题目大意】给出一个无向图，点有点权，边有边权。然后有Q个询问(X,Y)，表示求一条从X到Y的路径，其总代价为路上边权只和加上路径上点权最大的一个点的点权。询问就使这个总代价最少是多少？
【算法分析】
翻开《算法艺术与信息学竞赛》第308页就有这个题目。
我们假定了K为点权最大的点，那么显然，对于询问(X,Y)：W=D[X,K]+D[K,Y]+COST[K]。
其中D[X,K]和D[K,Y]表示删除权值比K大的点以后的最短路。
由于是无向图，再转变一下。
W=D[K,X]+D[K,Y]+COST[K]。
到了这一步。。。大家都知道怎么打表了吧。。。
我们就先预处理出D[i,j]表示从第i个出发，且所有点权>COST[i]的点都已删掉以后，到达j的最短路。
这可以用SPFA实现，复杂度O(NM)
然后打表，复杂度O(N^3)
【其他】我居然WA了4次，因为同一个问题：我把Case #xxx看成是题目给的方便你看的。。。没有输出。。。我那叫一个纠结吖~拿块豆腐撞死自己算了
【code】
#include
#define E 1000000
#define N 1000
using namespace std;
struct gtp{int x,y,w,next;}g[E];
int n,m,q,e,ls[N],ans[N][N],Vp[N],dist[N][N];
int d[N],list[N],v[N];
void add(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}
void init(){
memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++) scanf("%d",&Vp[i]);
e=0;
for (int i=1;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
}
void spfa(int st){
int head=0,tail=1; list[1]=st;
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++) d[i]=INF;
d[st]=0; v[st]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t!=0;t=g[t].next)
if (Vp[g[t].y]<=Vp[st] && d[g[t].x]+g[t].w
if (v[g[t].y]==0){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
}
void work(){
for (int i=1;i<=n;i++){
spfa(i);
for (int j=1;j<=n;j++) dist[i][j]=d[j];
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans[i][j]=INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++){
int tmp;
if (dist[k][i]==INF || dist[k][j]==INF) tmp=INF;
else tmp=dist[k][i]+dist[k][j]+Vp[k];
ans[i][j]=min(ans[i][j],tmp);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (ans[i][j]==INF) ans[i][j]=-1;
}
void print(){
for (int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%dn",ans[x][y]);
}
}
int main(){
int test=0;
for (;;){
scanf("%d%d%d",&n,&m,&q);
if (n+m+q==0) break;
test++;
if (test>1) printf("n");
init();
work();
printf("Case #%dn",test);
print();
}
return 0;
}