1、POJ1258
水水的prim……不过poj上硬是没过，wikioi上的原题却过了
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=,inf=1e8;
int d[maxn+],g[maxn+][maxn+],ans=,n;
bool v[maxn+];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
{
scanf("%d",&g[i][j]);
if(g[i][j]==) g[i][j]=inf;
}
memset(v,,sizeof(v));
for(int i=;i<=n;++i) d[i]=g[][i];
d[]=;
v[]=;
for(int j=;j<=n;++j)
{
int m=inf,k=j;
for(int i=;i<=n;++i)
if(v[i]==&&d[i]<m) m=d[i],k=i;
ans+=m;
v[k]=;
for(int i=;i<=n;++i)
if(v[i]==&&g[k][i]<d[i]) d[i]=g[k][i];
}
printf("%d",ans);
return ;
}
2、POJ1273
sap，不过就是在标号的时候有点小失误浪费了些时间，就是应该是d[1]=n+1时才推出，不然最后一次没有增广
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=,maxm=,inf=1e8;
struct wjmzbmr
{
int to,flow;
}e[maxm*+];
vector<int> g[maxn+];
int n,m,ans=,d[maxn+],dv[maxn+];
int dfs(int k,int flow)
{
if (k==n) return flow;
int s=;
for(int i=;i<g[k].size();++i)
{
wjmzbmr t=e[g[k][i]];
if(t.flow<=||d[k]!=d[t.to]+) continue;
int x=dfs(t.to,min(flow-s,t.flow));
e[g[k][i]].flow-=x;
e[g[k][i]^].flow+=x;
s+=x;
if(s==flow) return s;
}
if(d[]==n+) return s;
--dv[d[k]];
if(dv[d[k]]==) d[]=n+;
d[k]++;
dv[d[k]]++;
return s;
}
int main()
{
while (scanf("%d %d",&m,&n)!=EOF)
{
memset(dv,,sizeof(dv));
for(int i=;i<=n;++i) d[i]=;
ans=;
for(int i=;i<=n;++i) g[i].clear();
int l=;
for(int i=;i<=m;++i)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[l].to=b,e[l].flow=c,g[a].push_back(l);
++l;
e[l].to=a,e[l].flow=,g[b].push_back(l);
++l;
}
dv[]=n;
while(d[]<=n) ans+=dfs(,inf);
printf("%d\n",ans);
}
return ;
}
3、POJ1274
匈牙利算法，此题注意多组数据
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=;
int d[maxn+]={},n,m;
bool f[maxn+]={};
vector<int> g[maxn+];
bool dfs(int k)
{
for(int i=;i<g[k].size();++i)
if(!f[g[k][i]])
{
f[g[k][i]]=;
if(d[g[k][i]]==||dfs(d[g[k][i]]))
{
d[g[k][i]]=k;
return true;
}
}
return false;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=;i<=n+m;++i) g[i].clear();
for(int i=;i<=n;++i)
{
int x;
scanf("%d",&x);
for(int j=;j<=x;++j)
{
int y;
scanf("%d",&y);
g[i].push_back(y+n);
g[y+n].push_back(i);
}
}
memset(d,,sizeof(d));
for(int i=;i<=n;++i)
{
memset(f,,sizeof(f));
dfs(i);
}
int ans=;
for(int i=n+;i<=n+m;++i)
if(d[i]) ++ans;
printf("%d\n",ans);
}
}
4、POJ2182
平衡树，用treap写的
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<ctime>
const int maxn=;
int q[maxn+],ans[maxn+],n,p[maxn+]={};
struct wjmzbmr
{
wjmzbmr* ch[];
int size,value,key;
int cmp(int x)
{
if(x==value) return -;
return value<x;
}
void maintain()
{
size=;
if(ch[]!=NULL) size+=ch[]->size;
if(ch[]!=NULL) size+=ch[]->size;
}
};
wjmzbmr* root=NULL;
void rorate(wjmzbmr* &o,int d)
{
wjmzbmr *k=o->ch[d^];
o->ch[d^]=k->ch[d];
k->ch[d]=o;
o->maintain();
k->maintain();
o=k;
}
void insert(wjmzbmr* &o,int x)
{
if(o==NULL)
{
o=new wjmzbmr();
o->ch[]=o->ch[]=NULL;
o->size=;
o->value=x;
o->key=rand()%;
}
else
{
int d=o->cmp(x);
insert(o->ch[d],x);
if(o->ch[d]->key>o->key) rorate(o,d^);
}
o->maintain();
}
void remove(wjmzbmr* &o,int x)
{
int d=o->cmp(x);
if(d==-)
if(o->ch[]==NULL) o=o->ch[];
else
if(o->ch[]==NULL) o=o->ch[];
else
{
int d1=(o->ch[]->key>o->ch[]->key);
rorate(o,d1);
remove(o->ch[d1],x);
}
else remove(o->ch[d],x);
if(o!=NULL) o->maintain();
}
int kth(wjmzbmr* o,int k)
{
int l=;
if(o->ch[]!=NULL) l=o->ch[]->size;
if(l+==k) return o->value;
if(l+<k) return kth(o->ch[],k-l-);
if(l+>k) return kth(o->ch[],k);
}
int main()
{
freopen("ce.in","r",stdin);
freopen("ce.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",&q[i]);
for(int i=;i<=n;++i) insert(root,i);
for(int i=n;i>=;--i) ans[i]=kth(root,q[i]+),remove(root,ans[i]),p[ans[i]]=;
for(int i=;i<=n;++i) if(p[i]==) ans[]=i;
for(int i=;i<=n;++i) printf("%d\n",ans[i]);
return ;
}
5、POJ2186
有向图强联通，我用2次dfs写的，觉得挺好写的且可以直接撸出拓扑序列，尽管慢一些
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e5,inf=1e9;
vector < int > g[maxn+],g1[maxn+],g2[maxn+];
bool v[maxn+];
int n,m,color[maxn+],t[maxn+],len,c,d[maxn+];
void dfs(int k)
{
v[k]=;
for(int i=;i<g[k].size();++i)
if(!v[g[k][i]]) dfs(g[k][i]);
++len;
t[len]=k;
}
void dfs1(int k)
{
v[k]=;
color[k]=c;
for(int i=;i<g1[k].size();++i)
if(!v[g1[k][i]]) dfs1(g1[k][i]);
}
bool check2(int a,int b)
{
if(a==b) return ;
for(int i=;i<g2[a].size();++i)
if(g2[a][i]==b) return ;
return ;
}
int main()
{ while(scanf("%d %d",&n,&m)!=EOF)
{
c=;
len=;
memset(d,,sizeof(d));
for(int i=;i<=n;++i) g[i].clear(),g1[i].clear(),g2[i].clear();
for(int i=;i<=m;++i)
{
int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g1[y].push_back(x);
}
memset(v,,sizeof(v));
memset(t,,sizeof(t));
for(int i=;i<=n;++i) if(!v[i]) dfs(i);
memset(v,,sizeof(v));
for(int i=len;i>=;--i) if(!v[t[i]]) ++c,dfs1(t[i]);
for(int i=;i<=n;++i)
for(int j=;j<g[i].size();++j)
if(check2(color[i],color[g[i][j]]))
g2[color[i]].push_back(color[g[i][j]]),++d[color[i]];
int s=,x=;
for(int i=;i<=c;++i) if(d[i]==) ++s,x=i;
if(s>) printf("0\n");
else
{
int ans=;
for(int i=;i<=n;++i)
if(color[i]==x) ++ans;
printf("%d\n",ans);
}
}
return ;
}
6、POJ2187
凸包，求最远对，Andrew算法：水平竖直排序+正反两边维护 O(nlogn)
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=;
struct wjmzbmr
{
int x,y;
bool operator < (const wjmzbmr& a) const
{
return (x<a.x)||(x==a.x&&y<a.y);
}
}a[maxn+];
int n,s[maxn+],q[maxn+],m=,len=;
int cross(int x1,int y1,int x2,int y2)
{
return (x1*y2-y1*x2);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d %d",&a[i].x,&a[i].y);
sort(a+,a+n+);
m=;
s[]=,s[]=;
for(int i=;i<=n;++i)
{
while(m>=&&cross(a[s[m]].x-a[s[m-]].x,a[s[m]].y-a[s[m-]].y,a[i].x-a[s[m]].x,a[i].y-a[s[m]].y)<=) --m;
s[++m]=i;
}
s[++m]=n-;
int k=m;
for(int i=n-;i>=;--i)
{
while(m>=k&&cross(a[s[m]].x-a[s[m-]].x,a[s[m]].y-a[s[m-]].y,a[i].x-a[s[m]].x,a[i].y-a[s[m]].y)<=) --m;
s[++m]=i;
}
int ans=;
for(int i=;i<=m-;++i)
for(int j=i+;j<=m;++j)
if((a[s[i]].x-a[s[j]].x)*(a[s[i]].x-a[s[j]].x)+(a[s[i]].y-a[s[j]].y)*(a[s[i]].y-a[s[j]].y)>ans) ans=(a[s[i]].x-a[s[j]].x)*(a[s[i]].x-a[s[j]].x)+(a[s[i]].y-a[s[j]].y)*(a[s[i]].y-a[s[j]].y);
printf("%d",ans);
return ;
}
7、POJ2019
二维RMQ，但是有点细节要注意：就是以后打1<<(..)的时候一定要将整个都打上括号，因为<<优先级是最高的……这点小细节卡了不少时间
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=;
int mx[maxn+][maxn+][],mi[maxn+][maxn+][],n,b,m;
int qmax(int lx,int ly,int rx,int ry)
{
int r=int(log(double(ry-ly+))/log(double())),ans=-;
for(int i=lx;i<=rx;++i)
ans=max(ans,max(mx[i][ly][r],mx[i][ry-(<<r)+][r]));
return ans;
}
int qmin(int lx,int ly,int rx,int ry)
{
int r=int(log(double(ry-ly+))/log(double())),ans=1e8;
for(int i=lx;i<=rx;++i)
ans=min(ans,min(mi[i][ly][r],mi[i][ry-(<<r)+][r]));
return ans;
}
int main()
{
freopen("ce.in","r",stdin);
freopen("ce.out","w",stdout);
while(scanf("%d %d %d",&n,&b,&m)!=EOF)
{
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
{
scanf("%d",&mx[i][j][]);
mi[i][j][]=mx[i][j][];
}
int r=int(log(double(n))/log(double()));
for(int k=;k<=n;++k)
for(int j=;j<=r;++j)
for(int i=;i+(<<(j-))-<=n;++i)
{
mx[k][i][j]=max(mx[k][i][j-],mx[k][i+(<<(j-))][j-]);
mi[k][i][j]=min(mi[k][i][j-],mi[k][i+(<<(j-))][j-]);
}
for(int i=;i<=m;++i)
{
int lx,ly,rx,ry;
scanf("%d %d",&lx,&ly);
rx=min(n,lx+b-);
ry=min(ly+b-,n);
printf("%d\n",qmax(lx,ly,rx,ry)-qmin(lx,ly,rx,ry));
}
}
return ;
}
8、POJ1988
并查集，练练手
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=;
int f[maxn+],n,before[maxn+],len[maxn+];
int find(int x)
{
if(f[x]==x) return x;
int k=find(f[x]);
len[x]=len[k];
before[x]+=before[f[x]];
return f[x]=k;
}
int main()
{
scanf("%d\n",&n);
for(int i=;i<=n;++i) f[i]=i,len[i]=,before[i]=;
for(int i=;i<=n;++i)
{
char c;
scanf("%c ",&c);
if(c=='M')
{
int x,y;
scanf("%d %d\n",&x,&y);
x=find(x),y=find(y);
if(x!=y)
{
f[x]=y;
before[x]=len[y];
len[y]+=len[x];
}
}
else
{
int q;
scanf("%d\n",&q);
int k=find(q);
printf("%d\n",before[q]);
}
}
return ;
}
9、POJ3666
静态主席树求区间k小（此题是求中位数，左偏树也能搞）
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=;
struct wjmzbmr
{
int l,r,ls,rs,sum;
}f[maxn*];
struct fotile96
{
int l,r,mid;
}stack[maxn+];
int a[maxn+],sorta[maxn+],root[maxn+],n,len=;
int build(int l,int r)
{
int k=++len;
f[k].l=l,f[k].r=r,f[k].ls=f[k].rs=f[k].sum=;
if(l==r) return len;
int mid=(l+r)>>;
f[k].ls=build(l,mid);
f[k].rs=build(mid+,r);
return k;
}
int change(int root,int x)
{
int k=++len;
f[k]=f[root],f[k].sum+=;
if(f[k].l==f[k].r) return k;
int mid=(f[k].l+f[k].r)>>;
if(x<=mid) f[k].ls=change(f[k].ls,x);else f[k].rs=change(f[k].rs,x);
return k;
}
int ask(int a,int b,int k)
{
if(f[b].l==f[b].r) return f[b].r;
int mid=f[f[b].ls].sum-f[f[a].ls].sum;
if(k<=mid) return ask(f[a].ls,f[b].ls,k);else return ask(f[a].rs,f[b].rs,k-mid);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i) scanf("%d",&a[i]);
for(int i=;i<=n;++i) sorta[i]=a[i];
sort(sorta+,sorta+n+);
int q=;
for(int i=;i<=n;++i) if(sorta[i]!=sorta[q]) sorta[++q]=sorta[i];
root[]=build(,q);
for(int i=;i<=n;++i)
{
int x=lower_bound(sorta+,sorta+q+,a[i])-sorta;
root[i]=change(root[i-],x);
}
len=;
stack[len].l=stack[len].r=,stack[len].mid=a[];
for(int i=;i<=n;++i)
{
++len;
stack[len].l=stack[len].r=i,stack[len].mid=a[i];
while (len>&&stack[len].mid<stack[len-].mid)
{
stack[len-].r=stack[len].r;
--len;
stack[len].mid=sorta[ask(root[stack[len].l-],root[stack[len].r],(stack[len].r-stack[len].l+)/+)];
}
}
int ans=;
for (int i=;i<=len;++i)
for (int j=stack[i].l;j<=stack[i].r;++j)
ans+=abs(a[j]-stack[i].mid);
printf("%d",ans);
return ;
}