作者存档：edward_mj

[SGU206 Roads]KM算法的妙用

【题目大意】

给定N个城市和M条道路，其中前N-1条道路是大路，其它都是小路，并保证大 路可构成N个城市 的生成树。

第i条路费用为ci，要求你谎报费用（设第i条路上报的费用为di），使得对费用数组d来说，N-1条大路恰为最小生成树，并且sum|ci-di|尽可能小。

（摘自：http://crfish.blogbus.com/logs/62846336.html）

【算法分析】

本题的解题报告来自：http://wenku.baidu.com/view/7bfaa802de80d4d8d15a4faf.html

大概是这样：

令w[i]表示第i条路需要改变的量，且w[i]>=0

假设该路是大路，显然d[i]=c[i]-w[i];

假设该路是小路，显然d[i]=c[i]+w[i];

然后对于树环有限制条件：c[i]-w[i]<=c[j]+w[j]  (其中i为大路，j为小路)

变形成：w[i]+w[j]>=c[i]-c[j]。

于是KM里有不等式w[i]+w[j]>=P[i,j]。

然后由于最后KM的顶标之和等于最佳匹配的总权值，而对于该题而言，这个总权又是必须的。

于是两个问题等价了。

【CODE】

#include #include #include struct gtp{int x,y,w,op,next;}g[810];
int n,m,p,dis;
int w[405][405],fa[66],depth[66],lx[405],ly[405],link[405],ls[66];
bool cx[405],cy[405];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
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;
g[i].op=i+m;
}
for (int i=m+1;i<=2*m;i++){
g[i].x=g[i-m].y;
g[i].y=g[i-m].x;
g[i].w=g[i-m].w;
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
g[i].op=i-m;
}
}

void buildtree(int p){
for (int t=ls[p];t;t=g[t].next)
if ((t fa[g[t].y]=t;
depth[g[t].y]=depth[p]+1;
buildtree(g[t].y);
}
}

void buildgraph(){
memset(w,0,sizeof(w));
int i,x,y,Fa;
for (i=n;i<=m;i++){
x=g[i].x; y=g[i].y;
while (y!=x){
if (depth[x]>depth[y]) swap(x,y);
Fa=fa[y];
if (Fa>=n) Fa=g[Fa].op;
w[Fa][i-n+1]=max(0,g[Fa].w-g[i].w);
y=g[fa[y]].x;
}
}
p=max(n-1,m-n+1);
}

bool find(int i){
cx[i]=true;
int q;
for (int j=1;j<=p;j++)
if (lx[i]+ly[j]==w[i][j] && !cy[j]){
cy[j]=true;
q=link[j];
link[j]=i;
if (!q || find(q)) return true;
link[j]=q;
}
else if (!cy[j]) dis=min(dis,lx[i]+ly[j]-w[i][j]);
return false;
}

void KM(){
int i,j;
for (i=1;i<=p;i++)
for (j=1;j<=p;j++)
if (w[i][j]>lx[i])
lx[i]=w[i][j];
for (i=1;i<=p;i++){
for (;;){
for (j=1;j<=p;j++) cx[j]=false;
for (j=1;j<=p;j++) cy[j]=false;
dis=0x7FFFFFFF;
if (find(i)) break;
for (j=1;j<=p;j++) if (cx[j]) lx[j]-=dis;
for (j=1;j<=p;j++) if (cy[j]) ly[j]+=dis;
}
}
}

void output(){
for (int i=1;i<=p;i++) g[i].w-=lx[i];
for (int i=1;i<=p;i++) g[i+n-1].w+=ly[i];
for (int i=1;i<=m;i++)
printf("%dn",g[i].w);
}

int main(){
input();
buildtree(1);
buildgraph();
KM();
output();
}

[HDOJ3402 Ants run!]排序

【算法分析】
排序，然后判断就可以。
对于每只蚂蚁，我们只考虑他什么时候能追上前面那只蚂蚁就可以，因为被追上与之是对应的。
所以我们要尽量让后面那只蚂蚁难追上前面那只蚂蚁。
所以我们排序即可。
【CODE】
#include #include #include #include #include using namespace std;
const double pi=3.141592653589793238462643383279502884197169399375;
int n;
int a[100005];
double r;

void input(){
scanf("%d %lf",&n,&r);
for (int i=0;i scanf("%d",&a[i]);
r=2*r*pi/n;
}

void solve(){
double ans=1e50;
for (int i=1;i if (a[i]!=a[i-1] && r/(a[i]-a[i-1]) ans=r/(a[i]-a[i-1]);
if (ans==1e50) printf("Infn");
else printf("%.3lfn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
input();
sort(a,a+n);
solve();
}
}

[HDOJ3403 Palindrome day]暴力

【算法分析】
直接预处理出所有答案。
枚举回文数的前半截。
这样就可以确保升序。
注意判断闰年。
比赛时因为这个闰年的某个判断没AC。= =
【其它】
我真是沙茶。。。
【CODE】
#include #include #include typedef __int64 lld;
const int N=4000000;
int tot,Tc,len,odd;
lld list[4000005];
int L1[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int now,mid,dd,mm,Ed[10];
lld yy;
char ch[100];

inline lld filp(lld x){return x/10+x%10*10;}

void Add(int LL){
if (tot==N) return;
int i,j;
if (len%2==0) j=LL;
else j=LL-1;
while (j>0){
ch[++LL]=ch[j];
j–;
}
yy=dd*100+mm;
for (i=1;i<=LL;i++)
yy=yy*10+ch[i]-‘0’;
if (!((yy%4==0 && yy%100!=0) || yy%400==0))
if (filp(mm)==2 && filp(dd)==29) return;
yy=0;
for (i=1;i<=LL;i++)
yy=yy*10+ch[i]-‘0’;
list[++tot]=yy*10000+mm*100+dd;
}

void Try(){
int LL,i,j;
LL=(len+1)/2;
for (i=1;i<=LL;i++) ch[i]='0';
Add(LL);
if (tot==N) return;
while (1){
i=LL;
while (i>0 && ch[i]==’9′) i–;
if (i==0) return;
for (j=i+1;j<=LL;j++) ch[j]='0';
ch[i]++;
Add(LL);
if (tot==N) return;
}
}

bool can(){
int td=filp(dd),tm=filp(mm);
if (tm<1 || tm>12) return false;
if (td<1 || td>L1[tm]) return false;
return true;
}

void Get(){
for (dd=10;dd<=99;dd++)
for (mm=1;mm<=99;mm++)
if (can())
Try();
}

void init(){
tot=0;
for (len=0;tot Get();
Ed[len]=tot;
}
}

void PUT(lld x,int LL){
if (LL==0) return;
lld tmp=1;
for (int i=1;i while (tmp>0){
printf("%d",(int)(x/tmp%10));
tmp/=10;
}
}

void output(lld x,int LL){
PUT(x%100,2);
PUT(x/100%100,2);
PUT(x/10000,LL);
PUT(filp(x/100%100),2);
PUT(filp(x%100),2);
printf("n");
}

void solve(){
int Tc,x;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%d",&x);
int j=0;
while (x>Ed[j]) j++;
output(list[x],j);
}
}

int main(){
init();
solve();
}

HDU月赛——2010.5.1

本次月赛出了6题。Rank 2。
1002果断TLE。然后再用拓展欧几里得算法，再次WA到死。
然后最后rejudge了。
回文数的正解居然是要排序的，我写的是按顺序弄出来的。。。一路狂WA。。。
最后就这样悲剧了。
悲剧+沙茶。。。
没啥说的。。。BS我这沙茶吧
1001：http://hi.baidu.com/edwardmj/blog/item/7973c631706b6af41a4cff36.html
1002：http://hi.baidu.com/edwardmj/blog/item/432eec95b9c7bc6155fb9628.html
1003：http://hi.baidu.com/edwardmj/blog/item/bdd0b333ad4f3215ebc4af59.html
1004：http://hi.baidu.com/edwardmj/blog/item/b40d62d19d4bc038970a1612.html
1005：http://hi.baidu.com/edwardmj/blog/item/82fcbcc49ecc4f179d163d21.html
1006：http://hi.baidu.com/edwardmj/blog/item/46f4fcd30c4a34349b5027e2.html
1007：http://hi.baidu.com/edwardmj/blog/item/ddefd41529d7340d4a90a71c.html
另外1003在SCOI测试中，匹配是比并查集快的，但是这里匹配会TLE，只能用并差集。

[SPOJ2798 QTREE3]树链剖分、线段树

【题目地址】https://www.spoj.pl/problems/QTREE3/

【题目大意】
给定一棵树，一开始所有点都是白色的。
给定两个操作：
0 x：把点x变色（本来是白色变成黑色，本来是黑色变成白色）
1 x：求从结点1到点x的路径上，第一个黑色的点是哪一个？如果没有，输出-1。
【算法分析】
树链剖分例题(比本文详细)：http://hi.baidu.com/edwardmj/blog/item/2894235220a1be501038c2c9.html
首先显然把结点1当做根变成有根树。
轻重边剖分，然后都于每个重路径建立一棵线段树，然后对于操作0，就把线段树里对应那个点取反即可。
然后对于操作1，就从点x一直向父亲走，遇到重路径就跳到重路径的起始端，并用线段树取最小值，遇到轻边的话就直接走。
【其它】
跑了12s+。。。。果然我写的程序总是比较慢= =
【CODE】
#include #include #include const int N=100005;
const int INF=1000000000;
struct gtp{int x,y,next,op,inlist;}g[N*2];
struct TT{int l,r,zz;}tr[N*8];
int n,m,e,times,tot,ct,ans;
int ls[N],list[N],fa[N],Size[N],myheavy[N],black[N];
int color[N],cst[N];

void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void input(){
scanf("%d%d",&n,&m);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
}
}

void predfs(int p){
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (!fa[p] || t!=g[fa[p]].op){
fa[g[t].y]=t;
predfs(g[t].y);
}
Size[p]=times-Size[p];
}

void dfs(int p){
int mt,mm=-INF;
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && Size[g[t].y]>mm){
mm=Size[g[t].y];
mt=t;
}
if (mm==-INF) return;
myheavy[p]=mt;
list[++tot]=mt;
g[mt].inlist=tot;
dfs(g[mt].y);
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && t!=mt)
dfs(g[t].y);
}

void draw_color(){
ct=color[1]=cst[1]=1;
for (int i=2;i<=tot;i++){
if (g[list[i-1]].y!=g[list[i]].x) cst[++ct]=i;
color[i]=ct;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].zz=0;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}

void change(int p,int x){
if (tr[p].l==tr[p].r){
if (tr[p].zz) tr[p].zz=0;
else tr[p].zz=g[list[x]].x;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (x<=mid) change(p*2,x);
else change(p*2+1,x);
if (tr[p*2].zz) tr[p].zz=tr[p*2].zz;
else tr[p].zz=tr[p*2+1].zz;
}

void Get_zz(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r){
if (tr[p].zz) ans=tr[p].zz;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (r>mid) Get_zz(p*2+1,l,r);
if (l<=mid) Get_zz(p*2,l,r);
}

void Try(int x){
if (black[x]) ans=x;
if (x==1) return;
if (!g[fa[x]].inlist) Try(g[fa[x]].x);
else{
Get_zz(1,cst[color[g[fa[x]].inlist]],g[fa[x]].inlist);
Try(g[list[cst[color[g[fa[x]].inlist]]]].x);
}
}

void deal(){
for (int op,x,i=1;i<=m;i++){
scanf("%d%d",&op,&x);
if (op==0){
black[x]^=1;
if (myheavy[x]) change(1,g[myheavy[x]].inlist);
}else{
ans=0;
Try(x);
if (ans) printf("%dn",ans);
else printf("-1n");
}
}
}

int main(){
input();
predfs(1);
dfs(1);
draw_color();
build(1,1,tot);
deal();
}