POI2007
T1 旅游景点 首先很容易想到对每个关键点做一次最短路然后进行状压DP，不过暴力状压的复杂度是$k^22^k$的，会T，要去掉重复的状态变成$O(k2^k)$才能A，写了个记忆化搜索28S卡过
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20200
#define M 400400
using namespace std;
int n,m,i,j,k,x,y,z,h,t,w,Q,tot,ans,fir[N],q[N],dis[22][N],ne[M],la[M],va[M],a[22],dp[22][1050000];bool v[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int find(int x,int y){
if(dp[x][y]>=0)return dp[x][y];if(y==(1<<k)-1)return dis[x][n];dp[x][y]=1e9;
for(int i=2;i<=k+1;i++)if((y&a[i])==a[i])dp[x][y]=min(dp[x][y],dis[x][i]+find(i,y|(1<<(i-2))));
return dp[x][y];
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),memset(dis,0x3f,sizeof(dis)),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(w=1;w<=k+1;w++)for(memset(v,0,sizeof(v)),h=0,q[t=1]=w,dis[w][w]=0,v[w]=1;h!=t;)
for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(dis[w][x]+va[i]<dis[w][y=la[i]]){
dis[w][y]=dis[w][x]+va[i];
if(!v[y])v[q[t=t%n+1]=y]=1;
}
for(scanf("%d",&Q);Q--;)scanf("%d%d",&x,&y),a[y]|=1<<x-2;
memset(dp,-1,sizeof(dp));printf("%d",find(1,0));
}
T2 办公楼 很明显这题是要求补图并查集的每个联通块大小，但$n=10^5$，暴力构图是$n^2$的会T
考虑把目前剩余的点拉链，每次取出链头加入队列，把其原图中连边的点打标记，把链上没打标记的点删去，然后把删去的点加入队列，直到为空，那么目前队列里的元素就是一个联通块中的，然后清空队列继续操作
这样时间复杂度是$O(n+m)$的，达到了题目要求
#include<cstdio>
#include<algorithm>
#define N 100100
#define M 4004000
int n,m,x,y,i,tot,h,t,tm,cnt,fir[N],l[N],r[N],ne[M],la[M],ans[N],q[N],v[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=0;i<=n;i++)l[i]=i-1,r[i]=i+1;l[0]=n;r[n]=0;
for(;r[0];ans[++cnt]=t)
for(h=0,q[t=1]=r[0],l[r[r[0]]]=0,r[0]=r[r[0]];h^t;){
for(tm++,i=fir[x=q[++h]];i;i=ne[i])v[la[i]]=tm;
for(i=r[0];i;i=r[i])if(v[i]!=tm)q[++t]=i,l[r[i]]=l[i],r[l[i]]=r[i];
}
for(printf("%d\n",cnt),std::sort(ans+1,ans+cnt+1),i=1;i<=cnt;i++)printf("%d ",ans[i]);
}
T4 对称轴 可以把多边形剪下来，然后对于每个点保留其连接两条边的点积和×积，用Manacher算法，判断相等的条件是两个点点积和×积都相等，如果有长度大于等于1的回文串则符合条件。。代码是对的，但是最后一个数据跑了20S、
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400400
using namespace std;typedef long long LL;
struct W{LL x,y;}a[N],s[N];bool f;char ch;
bool operator==(W a,W b){return a.x==b.x&&a.y==b.y;}
W operator-(W a,W b){return W{a.x-b.x,a.y-b.y};}
LL operator*(W a,W b){return a.x*b.y-a.y*b.x;}
LL operator/(W a,W b){return a.x*b.x+a.y*b.y;}
int T,m,i,p,mx,ans,r[N];
void read(LL &x){
for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';if(f)x=-x;
}
int main(){
for(scanf("%d",&T);T--;ans=0){
for(scanf("%d",&m),i=1;i<=m;i++)read(a[i].x),read(a[i].y);
for(a[0]=a[m],a[m+1]=a[1],s[0].x=s[0].y=2e18,i=1;i<=m;i++){
s[2*i-1].x=(a[i]-a[i-1])*(a[i+1]-a[i]);
s[2*i-1].y=(a[i]-a[i-1])/(a[i+1]-a[i]);
s[2*i-1+2*m]=s[2*i-1];
}
for(memset(r,0,sizeof(r)),mx=p=0,i=1;i<=2*m;i++){
r[i]=mx>i?min(r[2*p-i],mx-i):1;
for(;s[i-r[i]]==s[i+r[i]];r[i]++);
if(i+r[i]>mx)mx=i+r[i],p=i;
if(i>m&&i<=2*m)if(r[i]>=m-(!(m&1)))ans++;
}
printf("%d\n",ans);
}
}
T5 Zap 感觉莫比乌斯反演又全部忘光啦，莫比乌斯反演基本就是$f(n)=\sum_{d|n} \mu{d/n}·F(d)$，然后一般$F(d)$一般是约数和或者倍数和，是比较好求的，可以利用$F(d)$反演求得$f(n)$
这道题很容易转化为$1\leq i\leq n,1\leq j\leq m$,求取出$(i,j)$使得$gcd(i,j)=1$的方案数，$F(i)=(n/i)*(m/i)$，则$f(i)=\sum \mu{d/i}(n/d)(m/d)$，但暴力求每次$O(n)$会T
考虑$(n/d)$只有$\sqrt{n}$个取值，$(n/d)(m/d)$只有$2\sqrt{n}$个取值，可以用容斥的方法得到每种取值快速更新答案
怎么容斥呢，$n/(n/i)$表示拥有$n/j=n/i$的最大的$j$，这样$i~j$这一段$n/(i~j)$的商相等，可以通过求出莫比乌斯函数前缀和$O(1)$得到该块答案
#include<cstdio>
#include<algorithm>
#define N 50050
using namespace std;
int n,m,i,j,pos,ans,t,Q,x,y,z,p[N],sum[N],u[N];bool f[N];
int main(){
for(n=50000,sum[1]=u[1]=1,i=2;i<=n;i++){
if(!f[i])p[++t]=i,u[i]=-1;
for(j=1;j<=t&&i*p[j]<=n;j++){
f[i*p[j]]=1;
if(i%p[j])u[i*p[j]]=-u[i];else break;
}
sum[i]=sum[i-1]+u[i];
}
for(scanf("%d",&Q);Q--;printf("%d\n",ans),ans=0){
scanf("%d%d%d",&x,&y,&z);n=x/z;m=y/z;if(n>m)swap(n,m);
for(i=1;i<=n;i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
}
}
}
T6 山峰和山谷 小学生难度的搜索，但写得比LCT还长，而且DFS直接爆栈了，懒得写了。。
#include<cstdio>
#define N 1010
int i,j,n,sz,ans1,ans2,a[N][N];bool f1[N*N],f2[N*N],v[N][N];
void dfs(int x,int y,int sz){
v[x][y]=1;
if(x>1){
if(a[x-1][y]==a[x][y]&&!v[x-1][y])dfs(x-1,y,sz);
if(a[x-1][y]<a[x][y])f1[sz]=1;if(a[x-1][y]>a[x][y])f2[sz]=1;
}
if(x<n){
if(a[x+1][y]==a[x][y]&&!v[x+1][y])dfs(x+1,y,sz);
if(a[x+1][y]<a[x][y])f1[sz]=1;if(a[x+1][y]>a[x][y])f2[sz]=1;
}
if(y>1){
if(a[x][y-1]==a[x][y]&&!v[x][y-1])dfs(x,y-1,sz);
if(a[x][y-1]<a[x][y])f1[sz]=1;if(a[x][y-1]>a[x][y])f2[sz]=1;
}
if(y<n){
if(a[x][y+1]==a[x][y]&&!v[x][y+1])dfs(x,y+1,sz);
if(a[x][y+1]<a[x][y])f1[sz]=1;if(a[x][y+1]>a[x][y])f2[sz]=1;
}
if(x>1&&y>1){
if(a[x-1][y-1]==a[x][y]&&!v[x-1][y-1])dfs(x-1,y-1,sz);
if(a[x-1][y-1]<a[x][y])f1[sz]=1;if(a[x-1][y-1]>a[x][y])f2[sz]=1;
}
if(x>1&&y<n){
if(a[x-1][y+1]==a[x][y]&&!v[x-1][y+1])dfs(x-1,y+1,sz);
if(a[x-1][y+1]<a[x][y])f1[sz]=1;if(a[x-1][y+1]>a[x][y])f2[sz]=1;
}
if(x<n&&y>1){
if(a[x+1][y-1]==a[x][y]&&!v[x+1][y-1])dfs(x+1,y-1,sz);
if(a[x+1][y-1]<a[x][y])f1[sz]=1;if(a[x+1][y-1]>a[x][y])f2[sz]=1;
}
if(x<n&&y<n){
if(a[x+1][y+1]==a[x][y]&&!v[x+1][y+1])dfs(x+1,y+1,sz);
if(a[x+1][y+1]<a[x][y])f1[sz]=1;if(a[x+1][y+1]>a[x][y])f2[sz]=1;
}
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(!v[i][j]){
dfs(i,j,++sz);
if(!f1[sz])ans1++;if(!f2[sz])ans2++;
}
printf("%d %d",ans2,ans1);
}
T7 大都市 傻逼树剖，套树状数组就行了，我写的是直接树剖的，但没想到还有比我短的，真是佩服
#include<cstdio>
#define N 252500
int n,i,x,y,tot,m,sum,ans,id,fir[N],la[N<<1],ne[N<<1],c[N],fa[N],bl[N],pos[N],h[N],sz[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}char s[9];
int qu(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
void dfs(int x){
int i,y;sz[x]=1;
for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i]))fa[y]=x,h[y]=h[x]+1,dfs(y),sz[x]+=sz[y];
}
void dfs2(int x,int f){
int now=0,i;pos[x]=++id;bl[x]=f;
for(i=fir[x];i;i=ne[i])if(sz[y=la[i]]>sz[now]&&h[x]<h[y])now=y;
if(!now)return;dfs2(now,f);
for(i=fir[x];i;i=ne[i])if(h[x]<h[y=la[i]]&&now!=y)dfs2(y,y);
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(1);dfs2(1,1);for(i=2;i<=n;i++)add(i,1);
for(scanf("%d",&m),m+=n-1;m--;){
scanf("%s",s);if(s[0]=='W'){
scanf("%d",&x);
for(ans=0;bl[1]!=bl[x];x=fa[bl[x]])ans+=qu(pos[x])-qu(pos[bl[x]]-1);
printf("%d\n",ans+qu(pos[x])-qu(pos[1]-1));
}else scanf("%d%d",&x,&y),add(pos[y],-1);
}
}
T8 洪水 首先按照高度拉链，对于相同高度的用并查集把周围比他低的并起来，此时若该块没有水泵，则需要放置一个水泵
#include<cstdio>
#define N 1001000
int i,x,p,q,n,m,k,fa[N],fir[1010],ne[N],sz[N],a[N];bool v[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void uni(int x,int y){p=gf(x);q=gf(y);if(p!=q)fa[q]=p,sz[p]+=sz[q];}
int main(){
for(scanf("%d%d",&n,&m),k=n*m,i=1;i<=k;i++){
scanf("%d",&a[i]);a[i]<=0?a[i]=-a[i]:v[i]=1;
fa[i]=i;ne[i]=fir[a[i]];fir[a[i]]=i;
}
for(x=1;x<=1000;x++){
for(i=fir[x];i;i=ne[i]){
if(i%m!=1&&a[i-1]<=a[i])uni(i,i-1);
if(i%m&&a[i+1]<=a[i])uni(i,i+1);
if(i>m&&a[i-m]<=a[i])uni(i,i-m);
if(i+m<=k&&a[i+m]<=a[i])uni(i,i+m);
}
for(i=fir[x];i;i=ne[i])if(v[i]&&!sz[gf(i)])sz[gf(i)]|=1;
}printf("%d",sz[gf(1)]);
}
T9 石头花园 首先把所有石头移到y=x一侧是最优的，答案就是移完后的长度差和宽度差和的两倍，现在的问题是算出最小代价
枚举四种可能的情况，长宽都不变，变任意一个或者都变，判断出四种情况的最小代价更新答案即可
#include<cstdio>
#define N 1001000
int n,i,now,lx=2e9,rx,ly=2e9,ry,x[N],y[N],w[N],v[N],ans[N];
void max(int&a,int b){if(a<b)a=b;}
void min(int&a,int b){if(a>b)a=b;}
void cal(int lx,int rx,int ly,int ry){
for(now=0,i=1;i<=n;i++){
if(lx<=x[i]&&x[i]<=rx&&ly<=y[i]&&y[i]<=ry){v[i]=0;continue;}
if(lx<=y[i]&&y[i]<=rx&&ly<=x[i]&&x[i]<=ry)v[i]=1,now+=w[i];else return;
}
if(now<ans[0])for(ans[0]=now,i=1;i<=n;i++)ans[i]=v[i];
}
int main(){
for(scanf("%d",&n),ans[0]=2e9,i=1;i<=n;i++){
scanf("%d%d%d",&x[i],&y[i],&w[i]);
if(x[i]<=y[i])min(lx,x[i]),max(rx,x[i]),min(ly,y[i]),max(ry,y[i]);
else min(lx,y[i]),max(rx,y[i]),min(ly,x[i]),max(ry,x[i]);
}printf("%lld ",2ll*(rx+ry-lx-ly));
cal(lx,rx,ly,ry);cal(ly,rx,lx,ry);cal(lx,ry,ly,rx);cal(ly,ry,lx,rx);
for(printf("%d\n",ans[0]),i=1;i<=n;i++)putchar(ans[i]?'1':'0');
}
T10 立方体大作战 从前往后扫，如果遇到已经出现的块，则把中间的一段合并，合并的代价是没有合并过的块的总数，这样用树状数组扫一遍就能得到答案了
#include<cstdio>
#define N 100050
int n,i,x,ans,sum,c[N],v[N];
void add(int x,int y){for(;x<=2*n;x+=x&-x)c[x]+=y;}
int qu(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int main(){
for(scanf("%d",&n),i=1;i<=2*n;i++){
scanf("%d",&x);
if(!v[x])v[x]=i,add(i,1);else ans+=qu(i)-qu(v[x]),add(v[x],-1);
}printf("%d",ans);
}
T11 驾驶考试 把所有边反向，然后相当于对每个$i$求一个从左边和右边需要修建路的数目，相当于求一个最长下降子序列，可以用set维护，要注意$x$相同时$y$要升序排列，因为这当中只能走1个，这样统计出从左边要修的路的数量$f[i]$和从右边走要修路的数量$g[i]$，然后直接单调扫一遍就可以出解了
#include<cstdio>
#include<set>
#include<algorithm>
#define N 100100
using namespace std;
int n,m,p,k,t1,t2,x,y,z,i,j,ans,now,f[N],g[N];
struct E{int x,y;}a[N],b[N];
multiset<int>st;multiset<int>::iterator it;
bool cmp(E a,E b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
bool cmp2(E a,E b){return a.x>b.x||a.x==b.x&&a.y<b.y;}
int main(){
for(scanf("%d%d%d%d",&n,&m,&p,&k);p--;){
scanf("%d%d%d",&x,&y,&z);
if(z)a[++t1].x=x+1,a[t1].y=y;else b[++t2].x=x,b[t2].y=y;
}
for(sort(a+1,a+t1+1,cmp),j=1,i=2;i<=n;f[i]=i-st.size()-1,i++)
for(;a[j].x==i;j++){
st.insert(a[j].y);
it=st.lower_bound(a[j].y);
if(it!=st.begin())st.erase(--it);
}
for(st.clear(),sort(b+1,b+t2+1,cmp2),j=1,i=n-1;i;g[i]=n-i-st.size(),i--)
for(;b[j].x==i;j++){
st.insert(b[j].y);
it=st.lower_bound(b[j].y);
if(it!=st.begin())st.erase(--it);
}
for(j=0,i=1;i<=n;i++){
for(;f[j+1]+g[i]<=k&&j<n;j++);
ans=max(ans,j-i+1);if(!f[i]&&!g[i])now++;
}
printf("%d",ans-now);
}
T12 天然气管道 画了几下觉得直接横坐标纵坐标各排一次序一一对应取应该没什么问题就A了，不过实在不知道300B的程序怎么写出来、
#include<cstdio>
#include<algorithm>
#define N 50050
using namespace std;
struct EG{int x,y;}a[N],b[N];
int n,i;long long ans;
bool cmp(EG a,EG b){return a.x<b.x;}
bool Cmp(EG a,EG b){return a.y<b.y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
for(i=1;i<=n;i++)scanf("%d%d",&b[i].x,&b[i].y);
sort(a+1,a+n+1,cmp);sort(b+1,b+n+1,cmp);for(i=1;i<=n;i++)ans+=b[i].x-a[i].x;
sort(a+1,a+n+1,Cmp);sort(b+1,b+n+1,Cmp);for(i=1;i<=n;i++)ans+=a[i].y-b[i].y;
printf("%lld",ans);
}
T13 堆积木 首先推出DP公式，$dp[i]=max(dp[j])+1(i>j,a[i]>a[j],a[i]-a[j]\geq i-j)$，但如果直接做是一个三维偏序，十分麻烦
把$a[i]-a[j]\geq i-j$和$a[i]>a[j]$相减惊奇地发现$i>j$，于是只要按$a[i]-a[j]$排序，用$a[i]$做LIS即可。。
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int n,i,l,r,mid,t,x,tot,q[N];
struct G{int x,y;}a[N];
bool cmp(G a,G b){return a.x>b.x||a.x==b.x&&a.y<b.y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%d",&x);
if(x<=i)a[++tot].y=x,a[tot].x=x-i;
}
for(sort(a+1,a+tot+1,cmp),i=1;i<=tot;i++){
if(a[i].y>a[q[t]].y)q[++t]=i;else{
for(l=1,r=t;l<r;)if(a[i].y>a[q[mid=l+r>>1]].y)l=mid+1;else r=mid;
q[l]=i;
}
}
printf("%d",t);
}
T14 砝码 首先答案具有可二分性，然后可以统计出每种砝码的质量和数量，不同的砝码也就30个，然后判断的时候将砝码和容器都从大到小排，对每个容器，如果大的砝码能放就尽量放，为什么这样是对的呢？因为大的是小的倍数，如果放若干个小的还不如放大的，如果所有砝码都放完了就可行，复杂度$O(30mlgm)$
看了下网上的题解，感觉和我的不太一样。。按位拆分真是醉了
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int i,j,n,m,now,tot,w,u,l,r,mid,ans,a[N],b[N];
struct P{int x,y;}p[N],q[N];
bool ok(int x){
for(now=0,i=1;i<=tot;i++)if(now+p[i].y<x)q[i]=p[i],now+=p[i].y;else {q[w=i]={p[i].x,x-now};break;}
for(i=n;i;i--)for(u=a[i],j=w;j;j--)if(u&&q[j].y)
if(u/q[j].x<=q[j].y)q[j].y-=u/q[j].x,u-=(u/q[j].x)*q[j].x;else u-=q[j].y*q[j].x,q[j].y=0;
for(i=1;i<=w;i++)if(q[i].y>0)return 0;return 1;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(sort(a+1,a+n+1),i=1;i<=m;i++)scanf("%d",&b[i]);
for(sort(b+1,b+m+1),i=now=1;i<=m;i++)if(b[i]==b[i+1])now++;else p[++tot]=P{b[i],now},now=1;
for(l=0,r=m;l<=r;)if(ok(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1;printf("%d",ans);
}
T15 四进制的天平 首先高精度转化为四进制，$f[i]$表示从前取的答案和方案数，$g[i]$表示从后取再减的答案和方案数，两个互相更新就可以得到答案$f[i]＝min(f[i+1]＋a[i],g[i+1]＋a[i]+1),g[i]＝min(f[i+1]＋4-a[i],g[i+1]＋3－a[i])$
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 1000000000
#define N 10010
using namespace std;
int n,i,tot,a[N],ff[N],gg[N],f[N],g[N];char s[N];
int main(){
for(scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;i++)s[i]-='0';
for(i=1;i<=n>>1;i++)swap(s[i],s[n-i+1]);
while(n){
for(i=n,s[0]=0;i>=1;i--)s[i-1]+=(s[i]&3)*10,s[i]>>=2;
a[++tot]=s[0]/10;for(;!s[n]&&n;n--);
}
for(ff[tot+1]=1,g[tot+1]=1e9,i=tot;i>=0;i--){
f[i]=f[i+1]+a[i];ff[i]=ff[i+1];
if(g[i+1]+a[i]+1<f[i])f[i]=g[i+1]+a[i]+1,ff[i]=gg[i+1];
else if(g[i+1]+a[i]+1==f[i])ff[i]=(ff[i]+gg[i+1])%M;
g[i]=g[i+1]+3-a[i];gg[i]=gg[i+1];
if(f[i+1]+4-a[i]<g[i])g[i]=f[i+1]+4-a[i],gg[i]=ff[i+1];
else if(f[i+1]+4-a[i]==g[i])gg[i]=(gg[i]+ff[i+1])%M;
}
printf("%d",ff[0]);
}
T16 Railway 先选任意一个关键点做一遍最短路，然后和剩下的点在最短路上连线，对所有连线中的点做一遍最小生成树，就可以得到较优解
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5010
#define M 1001000
using namespace std;
int n,m,i,h,t,x,y,w,tot,ans,a[N],f[N],fir[N],ne[M],la[M],va[M],d[N],q[N],pre[N];
struct P{int x,y,z;}p[M];bool v[N];
bool cmp(P a,P b){return a.z<b.z;}
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),ins(p[i].x,p[i].y,p[i].z),ins(p[i].y,p[i].x,p[i].z);
for(scanf("%d",&w),i=1;i<=w;i++)scanf("%d",&a[i]);
for(memset(d,63,sizeof(d)),d[q[t=1]=a[1]]=0,v[a[1]]=1;h^t;)
for(i=fir[x=q[h=h%n+1]],v[x]=0;i;i=ne[i])if(d[x]+va[i]<d[y=la[i]]){
d[y]=d[x]+va[i];pre[y]=x;
if(!v[y])v[q[t=t%n+1]=y]=1;
}
for(memset(v,0,sizeof(v)),v[a[1]]=i=1;i<=w;i++)for(x=a[i];!v[x];x=pre[x])v[x]=1;
for(sort(p+1,p+m+1,cmp),t=0,i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++)if(v[p[i].x]&&v[p[i].y]&&gf(p[i].x)!=gf(p[i].y))f[gf(p[i].x)]=gf(p[i].y),ans+=p[i].z,q[++t]=i;
for(printf("%d %d\n",ans,t),i=1;i<=t;i++)printf("%d %d\n",p[q[i]].x,p[q[i]].y);
}
评论 (0)
