分类存档：默认分类

【题目大意】 有n个人下棋，每次有两个人下，赢者留下再比(可以与刚下败的人)。给出每个人下的次数，要求出一种可行方案，输出每次比赛的过程，赢者放在第一列，败者放在第二列。

【算法分析】传说中的构造。。。看了别人的还不懂，然后再看了程序才懂= =
就是把那些人按出场的次数从大到小排序，然后让前面的人尽量赢，然后再按顺序填掉剩下的表就行了。
我看的是这个：http://www.cppblog.com/schindlerlee/archive/2010/01/27/106503.html?opt=admin
但是值得注意的是最后他说的那句剩下的随便填是绝对不行的，因为之前我写过一种方法。。。随便填最后会到自己打自己。应该是按照升序来填，这样就会尽量避免和自己打。

【其它】
994465 02.02.10 15:31 edward 138 .CPP Accepted 25 ms 827 kb
【CODE】
#include #include #include #include using namespace std;
struct datat{int d,mark;}a[111];
int n,ans[111111][2];

bool cmp(datat x,datat y){return x.d>y.d;}

int main(){
int sum=0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i].d);
a[i].mark=i;
sum+=a[i].d;
}
sort(&a[1],&a[n+1],cmp);
sum/=2;
printf("%dn",sum);
int tot=0;
for (int i=1;i<=n;i++){
while (tota[i].d–;
tot++;
ans[tot][0]=a[i].mark;
}   
if (tottot++;
ans[tot][1]=a[i].mark;
ans[tot][0]=a[i+1].mark;
a[i+1].d–;
a[i].d–;
}   
}
int top=1;
while (a[top].d==0) top++;
for (int i=1;i<=sum;i++){
printf("%d ",ans[i][0]);
if (ans[i][1]) printf("%d",ans[i][1]);
else{
printf("%d",a[top].mark);
a[top].d–;
while (a[top].d==0) top++;
}  
printf("n");
}
}   

【题目大意】 数轴上有N个区间，每个区间有一个权值C，你可以选择任意多的区间，但是数轴上某一段不能被覆盖超过K次，求最大能获得的权值。

【算法分析】这个连边感觉比较巧，不过挺容易理解。
就是先离散化，然后i向i+1连边，容量为limit，费用为0
然后再对于每个区间连边a[i]->b[i]，容量为1，费用为w[i]
新增源汇，连边[S,1]，容量为limit，费用为0
连边[n,T]，容量为limit，费用为0
实际到达每一个点的话就相当于选择是否分配流到以这个点位起点的区间边上，然后再向后流去。
做一次最大费用最大流即可。

【其它】1A
6401617 edward2 3680 Accepted 644K 407MS G++ 2404B 2010-02-02 18:50:17
【CODE】
#include #include #include #include using namespace std;
#define N 1000
struct gtp{int x,y,next,w,c,op;}g[10000];
int n,e,m,limit,cost;
int a[N],b[N],w[N],zb[N];
int ls[N],fa[N],d[N],v[N],list[N];

void init(){
scanf("%d%d",&m,&limit);
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&w[i]);
}

void lisan(){
int tail=0;
for (int i=1;i<=m;i++){
zb[++tail]=a[i];
zb[++tail]=b[i];
}
sort(&zb[1],&zb[tail+1]);
n=0;
for (int i=1;i<=tail;i++)
if (n==0 || zb[n]!=zb[i]) zb[++n]=zb[i];
}

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

int find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>zb[mid]) l=mid+1;
else r=mid;
}
return l;
}

void build(){
e=0; memset(ls,0,sizeof(ls));
for (int i=0;i<=n;i++) add(i,i+1,limit,0);
for (int i=1;i<=m;i++)
add(find(a[i]),find(b[i]),1,w[i]);
}

bool spfa(){
for (int i=0;i<=n+1;i++){
d[i]=-1;
v[i]=0;
}
d[0]=0; v[0]=1; list[0]=0;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
if (d[n+1]==-1) return false;
return true;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=n+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=n+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
cost+=nf*d[n+1];
}

void mincost_maxflow(){
cost=0;
while (spfa()) change();
}

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;i init();
lisan();
build();
mincost_maxflow();
printf("%dn",cost);
}
}

【题目大意】 给定一个无向图，图中有一个起点S和一个终点T。要求选K个集合S1，S2，…，SK，每个集合都含有图中的一些边，任意两个不同的集合的交集为空。并且从图中任意去掉一个集合，S到T都没有通路。要求K尽量大。

【算法分析】如果你会dinic的话，就很容易有感觉。。。
实际上就是弄一个层次图，设d[i]为从S到i点的最短路，然后每一个割集分别就是所有d[x]=dis和d[x]=dis+1相连的边的集合。

【其它】1A
994092 01.02.10 19:03 edward 213 .CPP Accepted 25 ms 23423 kb
【CODE】
#include #include #include #define N 500
struct gtp{int x,y,next;}g[2000000];
int n,e,S,T,ls[N],d[N],v[N],list[N];

void init(){
scanf("%d%d%d%d",&n,&e,&S,&T);
for (int i=1;i<=e;i++){
scanf("%d%d",&g[i].x,&g[i].y);
g[i+e].x=g[i].y;
g[i+e].y=g[i].x;
}
for (int i=1;i<=2*e;i++){
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
}   
}   

void spfa(){
memset(d,60,sizeof(d));
memset(v,0,sizeof(v));
d[S]=0; v[S]=1; list[0]=S;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (d[g[t].x]+1d[g[t].y]=d[g[t].x]+1;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}   
}
v[list[head]]=0;
}   
}

void print(){
printf("%dn",d[T]);
for (int dis=0;disint num=0;
for (int i=1;i<=n;i++)
if (d[i]==dis)
for (int t=ls[i];t;t=g[t].next)
if (d[g[t].y]==dis+1){
num++;
if (t>e) list[num]=t-e;
else list[num]=t;
}
printf("%d",num);
for (int i=1;i<=num;i++) printf(" %d",list[i]);
printf("n");
}   
}   

int main(){
init();
spfa();
print();
return 0;
}   

【题目大意】 有两个中转站，和N个点。每个点要么连到1号中转站，要么连到2号中转站。给出一些限制信息，即哪两个点必须连到一个中转站上，哪两个点必须不能连到一个中转站上。若两个点在同一中转站上，则距离是两者到中转站的距离和，否则是两者到中转站的距离和加上中转站之间的距离。求一种方案，使得任意两点之间的最大距离最小。

【算法分析】先二分枚举答案，将每只牛拆成连左边和连右边两个点，然后按以下方式连边进行2-SAT判定。（i表示连左边，i’表示连右边）
1、HATE I J ————->[I,J’]         [I’,J]        [J,I’]        [J’,I]
2、LOVE I J————-> [I,J]          [I’,J’]       [J,I]         [J’,I’]
3、这个根据题目的距离来搞，情况比较多，直接贴代码部分。。。
（d1[i]表示与第一个中转站的距离，d2[i]表示与第二个中转站的距离，d12为两个中转站的距离）
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
// ll
if (d1[i]+d1[j]>limit){
add(i,j+n);
add(j,i+n);
}
// lr
if (d12+d1[i]+d2[j]>limit){
add(i,j);
add(j+n,i+n);
}
// rl         
if (d12+d2[i]+d1[j]>limit){
add(i+n,j+n);
add(j,i);
}
// rr         
if (d2[i]+d2[j]>limit){
add(i+n,j);
add(j+n,i);
}   
}

【其它】1A
6398552 edward2 2749 Accepted 7096K 516MS G++ 2987B 2010-02-01 23:16:41
【CODE】
#include #include #include #define N 1200
#define inf 100000000
struct edge {int y,next;}g[1000000];
int n,a,b,ls[N],hate[2][N],love[2][N],x[N],y[N],sx1,sx2,sy1,sy2;
int d1[N],d2[N],d[501][501],d12,f[N],dep[N],color[N],e;

void init(){
scanf("%d%d%d",&n,&a,&b);
scanf("%d%d%d%d",&sx1,&sy1,&sx2,&sy2);
for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for (int i=1;i<=a;i++) scanf("%d%d",&hate[0][i],&hate[1][i]);
for (int i=1;i<=b;i++) scanf("%d%d",&love[0][i],&love[1][i]);
for (int i=1;i<=n;i++){
d1[i]=abs(x[i]-sx1)+abs(y[i]-sy1);
d2[i]=abs(x[i]-sx2)+abs(y[i]-sy2);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
d[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
d12=abs(sx1-sx2)+abs(sy1-sy2);
}

int gf(int k){
if (f[k]==k) return k;
f[k]=gf(f[k]);
return f[k];
}

void dfs(int k){
for (int t=ls[k];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[k]+1;
dfs(g[t].y);
if (dep[gf(g[t].y)] f[k]=f[g[t].y];
}
else if (!color[gf(g[t].y)] && dep[gf(g[t].y)] f[k]=f[g[t].y];
color[k]=1;
}

void tarjan(){
for (int i=1;i<=2*n;i++){
f[i]=i;
dep[i]=0;
color[i]=0;
}
for (int i=1;i<=2*n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
for (int i=1;i<=2*n;i++) gf(i);
}

void add(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

bool flag(int limit){
e=0; for (int i=1;i<=2*n;i++) ls[i]=0;
for (int i=1;i<=a;i++){
add(hate[0][i],hate[1][i]+n);
add(hate[1][i],hate[0][i]+n);
add(hate[0][i]+n,hate[1][i]);
add(hate[1][i]+n,hate[0][i]);
}
for (int i=1;i<=b;i++){
add(love[0][i],love[1][i]);
add(love[1][i],love[0][i]);
add(love[0][i]+n,love[1][i]+n);
add(love[1][i]+n,love[0][i]+n);
}
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++){
// ll
if (d1[i]+d1[j]>limit){
add(i,j+n);
add(j,i+n);
}
// lr
if (d12+d1[i]+d2[j]>limit){
add(i,j);
add(j+n,i+n);
}
// rl
if (d12+d2[i]+d1[j]>limit){
add(i+n,j+n);
add(j,i);
}
// rr
if (d2[i]+d2[j]>limit){
add(i+n,j);
add(j+n,i);
}
}
tarjan();
for (int i=1;i<=n;i++)
if (f[i]==f[i+n]) return false;
return true;
}

int main(){
init ();
if (!flag(inf)) printf("-1n");
else{
int l=0,r=inf,mid;
while (l mid=(l+r)/2;
if (flag(mid)) r=mid;
else l=mid+1;
}
printf("%dn",l);
}
return 0;
}

【题目大意】 有m道门, 开了前一道才能开后一道, 每道门上两把锁, 开一把就能开门, 这些锁并不是完全不同. 有2n把不同的钥匙, 每把对应一种锁, 这些钥匙被分成n对, 每对钥匙只能取其中的一把, 取其中一把, 另一把就会消失, 问最多能开几道门.

【算法分析】对每个类型的钥匙，拆成两个点，分别表示用这把钥匙和不用这把钥匙。然后二分答案，再利用题中的条件构造有向图，2-SAT判断就行了。

【其它】1A
6398374 edward2 2723 Accepted 860K 32MS G++ 1959B 2010-02-01 22:26:05
【CODE】
#include #include #include #define N 1<<18
struct edge{int y,next;}g[1000000];
int n,m,e,ls[N],need[2][N],op[N],f[N],dep[N],color[N];

void init(){
for (int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
op[x]=y;
op[y]=x;
}
for (int i=1;i<=m;i++) scanf("%d%d",&need[0][i],&need[1][i]);
}

int gf(int k){
if (f[k]==k) return k;
f[k]=gf(f[k]);
return f[k];
}

void dfs(int k){
for (int t=ls[k];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[k]+1;
dfs(g[t].y);
if (dep[gf(g[t].y)] }
else if (!color[gf(g[t].y)] && dep[gf(g[t].y)] f[k]=f[g[t].y];
color[k]=1;
}

void tarjan(){
for (int i=0;i<4*n;i++){
dep[i]=0;
f[i]=i;
color[i]=0;
}
for (int i=0;i<4*n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
for (int i=0;i<4*n;i++) gf(i);
}

inline void add(int x,int y){
e++;
g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

bool flag(int k){
if (k==0) return true;
e=0; for (int i=0;i<4*n;i++) ls[i]=0;
for (int i=0;i<2*n;i++){
add(i,op[i]+2*n);
add(i+2*n,op[i]);
}
for (int i=1;i<=k;i++){
add(need[0][i],need[1][i]+2*n);
add(need[1][i],need[0][i]+2*n);
}
tarjan();
for (int i=0;i<2*n;i++)
if (f[i]==f[i+2*n]) return false;
return true;
}

void work(){
int l=0,r=m,mid;
while (l+1 mid=(l+r)/2;
if (flag(mid)) l=mid;
else r=mid-1;
}
if (flag(r)) printf("%dn",r);
else printf("%dn",l);
}

int main(){
for (;;){
scanf("%d%d",&n,&m);
if (n+m==0) break;
init();
work();
}
return 0;
}