标签存档：图论

【题目大意】 有两个中转站，和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;
}

【题目大意】给定N个布尔型常量以及他们的一些运算结果，给出的运算包括and、xor、or，问能否找到一组常量的值使得它们满足这些约束？

【算法分析】2-SAT判定法。设i为false，i’为true
则对于约束这样连有向边（边[A,B]的意思是选了A，就必须选B）：
i and j=1————–>add(i,i’)   add(j,j’)
i and j=0————–>add(i’,j)   add(j’,i)
i or j=1—————->add(i,j’)   add(j’,i)
i or j=0—————->add(i’,i)   add(j’,j)
i xor j=1—————>add(i’,j)   add(j’,i)  add(i,j’)  add(j,i’)
i xor j=0—————>add(i,j)    add(i’,j’) add(j,i)    add(j’,i’)
然后用对于强连通缩点，如果i和i’在同一强连通分量，那么无解。（意思是选了i又必须选i‘，选了i’也必须选i）

【其它】2WA，因为C++的字符串读入是从0开始的，ORZ。。。思想还停留在用pascal的时候。。。悲剧。。。
6398008 edward2 3678 Accepted 1432K 438MS G++ 2290B 2010-02-01 21:07:17

【CODE】
#include #include #include struct edge{int y;edge *next;};
int f[2000],dep[2000],color[2000],n,m,e;
edge *ls[2000];

inline void add(int x,int y){
edge *p=new edge;
p->y=y; p->next=ls[x]; ls[x]=p;
}

// i means i (a[i]=0)
// i+n means i’ (a[i]=1)
void init(){
char op[1000];
scanf("%d %dn",&n,&m);
for (int i=0;i for (int i=1;i<=m;i++){
int x,y,ans;
scanf("%d %d %d %sn",&x,&y,&ans,&op);
if (op[0]==’A’){
if (ans){
add(x,x+n);
add(y,y+n);
// add(x+n,y+n); add(y+n,x+n); /*need?*/
}
else{
add(x+n,y);
add(y+n,x);
}
}
if (op[0]==’O’){
if (ans){
add(x,y+n);
add(y,x+n);
}
else{
add(x+n,x);
add(y+n,y);
// add(x,y); add(y,x); /*need?*/
}
}
if (op[0]==’X’){
if (ans){
add(x,y+n);
add(x+n,y);
add(y,x+n);
add(y+n,x);
}
else{
add(x,y);
add(y,x);
add(x+n,y+n);
add(y+n,x+n);
}
}
}
}

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

void dfs(int k){
for (edge *t=ls[k];t;t=t->next)
if (dep[t->y]==0){
dep[t->y]=dep[k]+1;
dfs(t->y);
if (dep[gf(t->y)] }
else if (color[gf(t->y)]==0 && dep[gf(t->y)] f[k]=f[t->y];
color[k]=1;
}

void tarjan(){
for (int i=0;i for (int i=0;i if (dep[i]==0){
dep[i]=1;
dfs(i);
}
for (int i=0;i}

bool print(){
for (int i=0;i if (f[i]==f[i+n]) return false;
return true;
}

int main(){
init();
tarjan();
if (print()) printf("YESn");
else printf("NOn");
return 0;
}

【题目来源】http://www.spoj.pl/problems/BOXES/

【题目大意】 N个盒子围成一圈，每个盒子里有A[I]个球，每向相邻的盒子移动一个球需要花费1的代价。求，最后所有盒子至少有一个球时花费的最小代价。

【算法分析】每个盒子看成一个点
1、连边[S,I]，容量为A[I],费用为0。
2、连边[I,T]，容量为1，费用为0。
3、连边[I,I+1]，容量为inf，费用为1
4、连边[I,I-1]，容量为inf，费用为1
求最小费用最大流即可。

【其它】1A
3230300 2010-02-01 12:41:33 cwj Boxes accepted 1.17 2.9M

C++

4.3.2

【CODE】
#include #include #include #define N 1002
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c,w;}g[10000];
int e,n,fa[N],d[N],ls[N],v[N],list[N],cost;

void addedge(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;
}   

void init(){
memset(ls,0,sizeof(ls));
e=0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
int x;
scanf("%d",&x);
addedge(0,i,x,0);
addedge(i,n+1,1,0);
addedge(i,i%n+1,inf,1);
addedge(i%n+1,i,inf,1);
}
}   

bool spfa(){
for (int i=0;i<=n+1;i++){
v[i]=0;
d[i]=inf;
}   
v[0]=1; d[0]=0; 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].wd[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]==inf) return false;
return true;
}   

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

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;iinit();
cost=0;
while (spfa()) change();
printf("%dn",cost);
}   
return 0;
}   

【题目大意】一个人K次从左上角走到右下角（只能向下走或向右走），走过格子可以把上面的分数取掉，取掉以后该分数变为0，求走K次得到的最大分数。

【算法分析】典型的费用流，将每个格子拆点，连一条边费用为A[I,J]，容量为1，另外一条边费用为0，容量为INF，剩下的不用说了。

【其它】1A
6397386 edward2 3422 Accepted 1316K 63MS G++ 2008B 2010-02-01 18:35:54 水过留痕

【CODE】
#include #include #define N 100000
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c,w;}g[1000000];
int n,S,T,e,ls[N],fa[N],d[N],cost,list[N],v[N];

void addedge(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 pos(int x,int y){
return (x-1)*n+y;
}

void init(){
int m;
scanf("%d%d",&n,&m);
S=0; T=n*n*2+1;
addedge(S,1,m,0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
int w;
scanf("%d",&w);
addedge(pos(i,j),pos(i,j)+n*n,1,w);
addedge(pos(i,j),pos(i,j)+n*n,inf,0);
if (i!=n) addedge(pos(i,j)+n*n,pos(i+1,j),inf,0);
if (j!=n) addedge(pos(i,j)+n*n,pos(i,j+1),inf,0);
}
addedge(n*n*2,T,inf,0);
}

bool spfa(){
for (int i=S;i<=T;i++){
d[i]=-1;
v[i]=0;
}
d[0]=0; list[0]=0; v[0]=1;
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[T]>-1) return true;
return false;
}

void change(){
cost+=d[T];
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}

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

int main(){
init();
maxflow_mincost();
printf("%dn",cost);
}