标签存档：图论

【题目大意】
给定一个有向带权图。1为源点，n为汇点。
求加一条权为无穷的边，并且改边的起始点和结束点都1V<=100
E<=V*(V-1)/2
【算法分析】
暴力加边判断肯定不可行。
于是，我们可以弄一个稍微不暴力的方法。
先对这个图求一次最大流。得到一个最小割。
我们加的边一定是这样的：起始点在源集合，结束点在汇集合。
那么dfs求出源集。
设加的边是然后我们将发现，加了边以后，新的增广路必然是这样的：S->p1->p2….->a->b->p3…->T。
于是我们可以从a->b这里截断两边分别求解。
就是在一开始最小割的残余网络中，
若i∈源集，那么FF[i]=maxFlow (S->i)
若i∈汇集，那么FF[i]=maxFlow (i->T)
最终答案将是Max ( Min(FF[i],FF[j]) + initFlow ) 其中i∈源集，j∈汇集。initFlow为原图最小割。
【其它】1Y。
【CODE】
#include #include #include #include using namespace std;
const int N=105;
struct edge{int x,y,c,next;}g[N*N],tg[N*N];
int n,m,e,S,T,Flow;
int ls[N],d[N],fa[N],cur[N],num[N],v[N],FF[N];

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

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

void relabel(int k){
cur[k]=ls[k];
int mm=n;
for (int t=ls[k];t;t=g[t].next)
if (g[t].c && d[g[t].y] mm=d[g[t].y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
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[fa[i]^1].c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
for (i=1;i<=n;i++){
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
num[0]=n;
i=S;
while (d[S] int &t=cur[i];
for (;t;t=g[t].next)
if (g[t].c && d[g[t].y]+1==d[g[t].x]) break;
if (t){
fa[g[t].y]=t;
i=g[t].y;
if (i==T){
change();
i=S;
}
}
else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=g[fa[i]].x;
}
}
}

void dfs(int p){
v[p]=1;
for (int t=ls[p];t;t=g[t].next)
if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}

void solve(){
memset(v,0,sizeof(v));
dfs(1);
for (int i=2;i<=e;i++) tg[i]=g[i];
int initFlow=Flow,ans=Flow;
for (int i=2;i if (v[i]){
S=1; T=i;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
else{
S=i; T=n;
Flow=0;
for (int j=2;j<=e;j++) g[j]=tg[j];
sap();
FF[i]=Flow;
}
for (int i=2;i for (int j=2;j if (v[i] && !v[j] && min(FF[i],FF[j])+initFlow>ans)
ans=min(FF[i],FF[j])+initFlow;
printf("%dn",ans);
}

int main(){
freopen("war.in","r",stdin);
freopen("war.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=0;i init();
S=1; T=n; Flow=0;
sap();
solve();
}
return 0;
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1475
【算法分析】
就是求一个二分图的最大点权独立集。
首先我们对图黑白染色，然后白的放X部，黑的放Y部。
再次假设我们取到所有格子上的权。
然后我们尝试最小割的一般构造方法。
对于X部点，如果属于割中源的那一边。那么就当做取这个点。如果属于汇的那一边，则不取。
对于Y部点，如果属于割中源的那一边。那么就当做不取这个点。如果属于汇的那一边，则取。
于是对应地连边。
对于i∈X部，那么连边S->i，容量应当是Wi。
对于i∈Y部，那么连边i->T，容量应当是Wi。
那么相邻的格子连边容量为INF.
对于割，证明命题：如果两点相邻，那么他们不会同时取。
先假设他们同时取了。
对于X部点，被割在了源那一边。
对于Y部点，被割在了汇那一边。
那么：这两点之间那条边，就成了割边！
又由于它是容量为INF的。那么不可能成为割边。
于是反证得上面的命题成立。
最后本题用最小割完美解决。
【其它】1Y。
【CODE】
#include #include #include const int N=35;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}g[205555],*ls[N*N],*cur[N*N],*fa[N*N];
int n,S,T,e,Flow,Sum;
int color[N][N],num[N*N],d[N*N];

int pos(int x,int y){
if (x<1 || x>n || y<1 || y>n) return -100000;
return (x-1)*n+y;
}

void addedge(int x,int y,int c){
if (x<0 || y<0) return;
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
scanf("%d",&n);
S=0; T=n*n+1;
e=0; memset(ls,0,sizeof(ls));
Sum=0;
for (int i=1;i<=n;i++)
for (int w,j=1;j<=n;j++){
if (j==1) color[i][j]=1-color[i-1][j];
else color[i][j]=1-color[i][j-1];
scanf("%d",&w);
Sum+=w;
if (color[i][j]){
addedge(S,pos(i,j),w);
addedge(pos(i,j),pos(i-1,j),INF);
addedge(pos(i,j),pos(i+1,j),INF);
addedge(pos(i,j),pos(i,j-1),INF);
addedge(pos(i,j),pos(i,j+1),INF);
}
else addedge(pos(i,j),T,w);
}
}

void relabel(int p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] d[p]=mm+1;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c Flow+=nf;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++){
d[i]=num[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}

int main(){
init();
sap();
printf("%dn",Sum-Flow);
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1565
【算法分析】
恩，就是比较裸的最大权闭合图，但是要知道如果形成环的话，网络流是处理不了的。
于是拓扑排序去环，然后最大权闭合图。
【其它】
今天见到NOI2009那里居然有一题未A= =，于是写一个练练手。
1Y。
NOI2009里的送分题。
【CODE】
#include #include const int N=1000;
const int E=1005555;
struct edge{int x,y,c;edge *next,*op;};
struct Node{int x,y;Node *next;};
struct Lint_t{
Node *ls[N],g[E];
int e;
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}
}Link;
struct Network_t{
int Flow,e,S,T;
edge *ls[N],*fa[N],*cur[N],g[E];
int num[N],d[N];
void addedge(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void relabel(int k){
cur[k]=ls[k];
int mm=T;
for (edge *t=ls[k];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
Flow+=nf;
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++) {
num[i]=0;
d[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}
else{
if (! –num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}
}Network;

int n,m,Sum;
int W[N],pos[50][50],L[N],du[N],v[N];

void init(){
scanf("%d%d",&m,&n);
int cnt=0,i,j,k,x,y;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
pos[i][j]=++cnt;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
scanf("%d%d",&W[pos[i][j]],&cnt);
for (k=0;k scanf("%d%d",&x,&y);
x++; y++;
Link.addedge(pos[i][j],pos[x][y]);
du[pos[x][y]]++;
}
if (j>1){
Link.addedge(pos[i][j],pos[i][j-1]);
du[pos[i][j-1]]++;
}
}
}

void topsort(){
int head=0,tail=0,i;
n*=m;
for (i=1;i<=n;i++)
if (!du[i]) L[++tail]=i;
while (head!=tail){
head++;
for (Node *t=Link.ls[L[head]];t;t=t->next){
du[t->y]–;
if (!du[t->y]) L[++tail]=t->y;
}
}
memset(v,0,sizeof(v));
for (int i=1;i<=tail;i++)
v[L[i]]=1;
}

void build(){
Network.S=0; Network.T=n+1;
Sum=0;
for (int i=1;i<=n;i++) if (v[i]){
for (Node *t=Link.ls[i];t;t=t->next)
if (v[t->y])
Network.addedge(t->y,i,0x7FFFFFFF);
if (W[i]>0){
Network.addedge(0,i,W[i]);
Sum+=W[i];
}
else Network.addedge(i,n+1,-W[i]);
}
}

int main(){
Link.e=Network.e=0;
memset(Link.ls,0,sizeof(Link.ls));
memset(Network.ls,0,sizeof(Network.ls));
init();
topsort();
build();
Network.sap();
printf("%dn",Sum-Network.Flow);
}

【题目大意】
给定N个数，让你取最多的数，使得取出的数里，不存在A是B的倍数这种情况。
【算法分析】
虽然当时ACM_DIY群赛时蒙对了算法，当时推理方式见（那叫一个强力）：
http://hi.baidu.com/edwardmj/blog/item/1ae99b3f5f5cbee53d6d9789.html
但一直没有理解，于是今天重温二分图时回来做了一下。
本题可以先把相同的数去掉，然后若A为B的倍数，那么B->A。
由于A>B，那么是一个DAG图（有向无环图）
然后DAG图的最大反链就可以利用匹配来搞。（传递闭包后的DAG图的最大独立集=最大反链）
具体做法是每个点拆两个点，弄成二分图，然后匹配。最后输出n-匹配数。
二分图总结见：http://hi.baidu.com/edwardmj/blog/item/b5fc0419bd3661f1af513325.html
小菜总结，不足谢谢补充。
【CODE】
#include #include #include const int N=1005;
typedef __int64 lld;
struct edge{int y;edge *next;}g[1005555],*ls[N];
int n,e,cnt;
int v[N],link[N];
lld a[N];

int cmp(const void *A,const void *B){
lld AA=*((lld*)A),BB=*((lld*)B);
if (AA>BB) return 1;
if (AA return 0;
}

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

void build(){
int tot=0,i,j;
for (i=1;i<=n;i++)
if (!tot || a[i]!=a[tot])
a[++tot]=a[i];
n=tot;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
if (a[j]%a[i]==0 && a[j]>a[i])
addedge(i,j);
}

bool Find(int p){
for (edge *t=ls[p];t;t=t->next)
if (v[t->y]!=cnt){
v[t->y]=cnt;
int q=link[t->y];
link[t->y]=p;
if (!q || Find(q)) return true;
link[t->y]=q;
}
return false;
}

void solve(){
memset(link,0,sizeof(link));
memset(v,0,sizeof(v));
int ans=0;
for (cnt=1;cnt<=n;cnt++)
if (Find(cnt)) ans++;
printf("%dn",n-ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
e=0;
for (int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
ls[i]=NULL;
}
qsort(a+1,n,sizeof(lld),cmp);
build();
solve();
}
}

【题目大意】
给一个无向图，对于每个点，求他是否在一个奇环中。如果不是ans++。输出ans。
【算法分析】
先求点的双连通分量，然后对于每个双连通分量，如果他里面有奇环，那么整个双连通分量上的点都在某奇环上。（这个可以用可以用奇偶性证明，实际上就是把整个图搞成两个有重叠部分的环）
然后判断一个双连通分量里有无奇环就可以交替染色。如果出现一条边的两端颜色相等，那么有奇环。
否则无奇环（利用反证法证明）
【其它】
原来我一直用的那个自创的沙茶并查集类Tarjan思想的算的是边的双连通分量，而不是点的双连通分量。于是果断WA到沙茶。。。哎，算法问题。。。
然后终于下定决心学习正版的Tarjan。学习结束重写1Y。
【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define clr(T) memset(T,0,sizeof(T))
const int N=1005;
struct edge{int x,y,next;}g[N*N];
int n,m,times,tot,e,Qt,cnt,check;
int a[N][N],ls[N],vis[N];
int DFN[N],done[N],Stack[N*N],low[N],Q[N*N],color[N*N],odd[N];

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

void init(){
int i,j,x,y;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j]=i!=j;
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=0;
}
times=tot=cnt=0;
e=1;
clr(ls);
clr(vis);
clr(DFN);
clr(done);
clr(low);
clr(odd);
for (i=1;i for (j=i+1;j<=n;j++)
if (a[i][j]){
addedge(i,j);
addedge(j,i);
}
}

void draw(int x){
vis[x]=cnt;
for (int t=ls[x];t;t=g[t].next)
if (color[t]==cnt && vis[g[t].y]!=cnt){
odd[g[t].y]=1-odd[x];
draw(g[t].y);
}else
if (color[t]==cnt && vis[g[t].y]==cnt && odd[g[t].y]==odd[x])
check=1;
}

void solve(int x){
cnt++;
for (int i=1;i<=Qt;i++){
color[Q[i]]=cnt;
color[Q[i]^1]=cnt;
}
check=0;
odd[x]=1;
draw(x);
if (check)
for (int i=1;i<=Qt;i++)
done[g[Q[i]].x]=done[g[Q[i]].y]=1;
}

void dfs(int x,int fa){
DFN[x]=low[x]=++times;
for (int t=ls[x];t;t=g[t].next){
int y=g[t].y;
if (y==fa) continue;
if (!DFN[y]){
Stack[++tot]=t;
dfs(y,x);
low[x]=min(low[x],low[y]);
if (DFN[x]<=low[y]){
Qt=0;
while (Stack[tot]!=t)
Q[++Qt]=Stack[tot–];
Q[++Qt]=Stack[tot–];
solve(x);
}
}else if (DFN[y] Stack[++tot]=t;
low[x]=min(low[x],DFN[y]);
}
}
}

void Tarjan(){
for (int i=1;i<=n;i++)
if (!DFN[i])
dfs(i,0);
}

int main(){
for (;;){
scanf("%d%d",&n,&m);
if (!n) break;
init();
Tarjan();
int ans=0;
for (int i=1;i<=n;i++)
if (!done[i]) ans++;
printf("%dn",ans);
}
return 0;
}