标签存档：图论

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1532
【算法分析】
二分答案然后，将比赛分配给选手，判定能不能分完。
这个用最大流实现。
【其它】sap被卡。HLPP被卡。。。于是dinic。。。
于是你可以见识到什么叫卡过。。。
34 30276 edward_mj 3164K 4772MS G++ 2.39K 2010-06-16 01:39:26 【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
const int N=20005;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}*ls[N],*cur[N],*fa[N];
int n,m,vs,vt,Flow;
int d[N],lx[N],ly[N],v[N],Q[N];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&lx[i],&ly[i]);
vs=0; vt=n+m+1;
}

inline void addedge(int x,int y,int c){
edge *p=(edge*)malloc(sizeof(edge));
edge *q=(edge*)malloc(sizeof(edge));
p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
}

bool bfs(){
for (int i=vs;i<=vt;i++){
d[i]=INF;
v[i]=0;
cur[i]=ls[i];
}
d[vs]=1; Q[1]=vs;
for (int st=1,ed=1;st<=ed;st++)
for (edge *t=ls[Q[st]];t;t=t->next)
if (t->c && d[t->y]==INF){
d[t->y]=d[t->x]+1;
Q[++ed]=t->y;
if (t->y==vt) return true;
}
return false;
}

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

void dinic(){
int i;
while (bfs()){
i=vs;
while (cur[vs]){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->x]+1==d[t->y] && !v[t->y]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==vt){
change();
i=vs;
}
}else{
v[i]=1;
if (i!=vs) i=fa[i]->x;
}
}
}
}

bool Can(int Limit){
for (int i=vs;i<=vt;i++)
while (ls[i]){
edge*t=ls[i];
ls[i]=t->next;
free(t);
}
for (int i=1;i<=m;i++){
addedge(vs,i,1);
addedge(i,m+lx[i],1);
addedge(i,m+ly[i],1);
}
for (int i=1;i<=n;i++) addedge(m+i,vt,Limit);
Flow=0;
dinic();
if (Flow==m) return true;
return false;
}

void solve(){
int l=m/n,r=m,mid;
while (l mid=(l+r)/2;
if (Can(mid)) r=mid;
else l=mid+1;
}
printf("%dn",l);
}

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

【题目大意】
知道之前的比赛结果，和将要打的对阵。问DD有没有可能得冠军？（不能是并列冠军）
【算法分析】
很直观的想法，剩余的对阵里，如果有DD，那么让DD赢。
否则设为未群定比赛。
然后最后构一个二分图，把比赛分给那些人。
那些人还能剩多少场允许胜，那么就连这么多容量的边。
大概这样。
【其它】。。。之前WA成SB，重写1Y。泪流满面。
居然跑了个第一，照个相，不然马上被刷下来了。

【CODE】
#include #include #include #define clr(a) memset(a,0,sizeof(a))
const int maxn=55;
const int N=20005;
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
edge *ls[N],*cur[N],*fa[N];
int d[N],gap[N],Flow,S,T;
void init(int n){
for (int i=0;i<=n;i++)
while (ls[i]){
edge *t=ls[i];
ls[i]=t->next;
free(t);
}
}

void addedge(int x,int y,int c){
edge *p=(edge*)malloc(sizeof(edge));
edge *q=(edge*)malloc(sizeof(edge));
p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
}

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

void change(){
int NF=0x7FFFFFFF;
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 n){
int i;
Flow=0;
for (i=0;i<=n;i++){
cur[i]=ls[i];
d[i]=0;
gap[i]=0;
}
gap[0]=n+1;
i=S;
while (d[S]<=n){
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 (!–gap[d[i]]) return;
relabel(i,n);
gap[d[i]]++;
if (i!=S) i=fa[i]->x;
}
}
}
}Network;

int n,m,cnt,NL;
int win[maxn];
char Name[maxn][22];

int Get(char *str){
int i,j;
bool flag;
for (i=1;i<=n;i++){
flag=true;
for (j=0;j<22;j++)
if (str[j]!=Name[i][j]){
flag=false;
break;
}
if (flag) return i;
}
n++;
for (j=0;j<22;j++) Name[n][j]=str[j];
return n;
}

void init(){
clr(Name);
clr(win);
Network.init(N-1);
char s1[22],s2[22],s3[22];
n=1; Name[1][0]=Name[1][1]=’D’;
for (int x,y,i=1;i<=m;i++){
clr(s1); clr(s2); clr(s3);
scanf("%s%s%s",s1,s2,s3);
x=Get(s1);
y=Get(s2);
if (s3[0]==’w’) win[x]++;
else win[y]++;
}

Network.S=0; Network.T=1; cnt=0;
scanf("%d",&m);
for (int x,y,i=1;i<=m;i++){
clr(s1); clr(s2);
scanf("%s%s",s1,s2);
x=Get(s1);
y=Get(s2);
if (x==1) win[1]++;
if (y==1) win[1]++;
if (x!=1 && y!=1){
cnt++;
Network.addedge(x,NL+cnt,1);
Network.addedge(y,NL+cnt,1);
Network.addedge(NL+cnt,Network.T,1);
}
}
}

bool solve(){
for (int i=2;i<=n;i++)
if (win[i]>=win[1]) return false;
for (int i=2;i<=n;i++)
Network.addedge(Network.S,i,win[1]-win[i]-1);
Network.sap(NL+cnt);
if (Network.Flow==cnt) return true;
return false;
}

int main(){
clr(Network.ls);
while (scanf("%d%d",&NL,&m)!=EOF){
init();
if (solve()) puts("Yes");
else puts("No");
}
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1822
【算法分析】
非常裸的模型。
求圆到线段的距离可以利用海伦公式+勾股定理。
然后剩下的就是二分时间+一个二分图匹配了。因为巫妖可能发多次，所以用网络流实现。
【其它】之前WA了∞遍，今天重敲。。。我靠，1Y。
【CODE】
#include #include #include #include #include #define sqr(x) ((x)*(x))
#define eps 1e-6
using namespace std;
const int maxn=205*2;
int Li,Wi,Tr;
bool v[maxn][maxn];
struct Lich_t{int x,y,r,t;}Lich[maxn];
struct Wise_t{int x,y;}Wise[maxn];
struct Tree_t{int x,y,r;}Tree[maxn];
struct Graph_t{
struct edge{int x,y,c;edge *next,*op;}g[maxn*maxn*4],*ls[maxn],*cur[maxn],*fa[maxn];
int d[maxn],gap[maxn],Flow,e,S,T;

void clr(){e=0; memset(ls,0,sizeof(ls));}

void add(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 p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[p]=mm+1;
}

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

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

inline int dis(int &X1,int &Y1,int &X2,int &Y2){return sqr(X1-X2)+sqr(Y1-Y2);}
inline double S(double &a,double &b,double &c){
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}

bool Can(Lich_t L,Wise_t W){
if (dis(L.x,L.y,W.x,W.y)>sqr(L.r)) return false;
for (int i=1;i<=Tr;i++){
Tree_t &T=Tree[i];
double a,b,c,d;
a=sqrt(dis(W.x,W.y,T.x,T.y));
b=sqrt(dis(W.x,W.y,L.x,L.y)); if (b==0) b=eps;
c=sqrt(dis(L.x,L.y,T.x,T.y));
if (b*b+c*c>a*a && a*a+b*b>c*c) d=S(a,b,c)*2/b;
else d=min(a,c);
if (d+eps<=T.r) return false;
}
return true;
}

void init(){
ios::sync_with_stdio(false);
memset(v,false,sizeof(v));
cin >> Li >> Wi >> Tr;
for (int i=1;i<=Li;i++)
cin >> Lich[i].x >> Lich[i].y >> Lich[i].r >> Lich[i].t;
for (int i=1;i<=Wi;i++)
cin >> Wise[i].x >> Wise[i].y;
for (int i=1;i<=Tr;i++)
cin >> Tree[i].x >> Tree[i].y >> Tree[i].r;
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (Can(Lich[i],Wise[j]))
v[i][j]=true;
}

bool Try(int Limit){
G.clr(); G.S=Li+Wi+1; G.T=Li+Wi+2;
for (int i=1;i<=Li;i++)
G.add(G.S,i,Limit/Lich[i].t+1);
for (int i=1;i<=Wi;i++)
G.add(Li+i,G.T,1);
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (v[i][j]) G.add(i,Li+j,1);
G.sap();
if (G.Flow==Wi) return true;
return false;
}

void solve(){
int l=0,r=1000000000,mid;
while (l mid=(l+r)/2;
if (Try(mid)) r=mid;
else l=mid+1;
}
if (!Try(l)) cout << "-1n";
else cout << l << "n";
}

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

【题目链接】http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6
或者八中：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1776
不过八中由于是Windows，所以要手写栈~没事可以去写一写~
Pascal的话就不用怕了，直接开编译开关：{$M 10000000}
【题目大意】
n<=20 0000
树上的每个点都涂了一种颜色，
对于每种颜色，问属于这种颜色的点中的最远点对是多少?
边权全是1。
时限2s per data
【算法分析】
做法1：
一开始看比较直观的就是对树进行基于点的分治。
时间复杂度O(n lg n)。
空间复杂度O(n lg n)。
但是由于常数过大，终究逃脱不了TLE的命运。

做法2：
首先我们画出一棵树。
然后可以发现,无论怎么画，对于同一种颜色，最长路出现时，其中一个点必然是这颗树中深度最大的点。
下面给出我的证明：
设x,y,z为三个同颜色的点，x为所有该种颜色中的深度最大的一个点。
那么我们现在要证命题：dis(y,z)<=max(dis(x,y),dis(x,z))。

可以用这个图先直观地感受一下。
下面我们采用反证法。
题设：dis(y,z)>max(dis(x,y),dis(x,z))。
将这个不等式转化成一个不等式组：
dep[x]+dep[y]-dep[LCA(x,y)]*2dep[x]+dep[z]-dep[LCA(x,z)]*2dep[x]-dep[z]<(dep[LCA(x,y)]-dep[LCA(y,z)])*2  ————①
dep[x]-dep[y]<(dep[LCA(x,z)]-dep[LCA(y,z)])*2  ————② 我们对这个两个不等式进行放大，得：
dep[LCA(x,y)]-dep[LCA(y,z)]>0
dep[LCA(x,z)]-dep[LCA(y,z)]>0
（之所以可以这样做，是因为dep[x]>=dep[z] && dep[x]>=dep[y]）

下面进行分类讨论：
1、dep[LCA(x,y)]<=dep[LCA(y,z)]。那么①式显然不成立。矛盾。
2、dep[LCA(x,y)]>dep[LCA(y,z)]。那么z的位置有两种可能。
①z是y的子孙。这样显然与题设矛盾。因为dis(x,z)>=dis(y,z)。（x到z的路径包括了y到z的路径）
②LCA(y,z)在“LCA(x,y)到y”的路径上。那么在这种情况下，我们看②式。

显然，此时LCA(x,z)=LCA(y,z)，所以②式不可能成立。于是又与题设矛盾。
所以，综上所述，①②两式不可能同时成立。于是题设不可能成立。
于是反证出命题：dis(y,z)<=max(dis(x,y),dis(x,z)) 正确。 有这个了结论，那么就可以找出每种颜色里深度最大的。然后其它的点都和它算一下距离就可以了。这里面用到了最近公共祖先(LCA)的经典算法。
【时间复杂度】O(n)
【空间复杂度】O(n)
【其它】这个代码在衡阳八中A不了，因为会栈溢出。
【时间和空间状况】
> Run 1: OK [0.011 secs, 8600 KB]
> Run 2: OK [0.011 secs, 8600 KB]
> Run 3: OK [0.022 secs, 8600 KB]
> Run 4: OK [0.022 secs, 8600 KB]
> Run 5: OK [0.011 secs, 8600 KB]
> Run 6: OK [0.140 secs, 11636 KB]
> Run 7: OK [0.151 secs, 11372 KB]
> Run 8: OK [0.378 secs, 15116 KB]
> Run 9: OK [0.367 secs, 13972 KB]
> Run 10: OK [0.464 secs, 17840 KB]
> Run 11: OK [0.572 secs, 17924 KB]
> Run 12: OK [0.745 secs, 22880 KB]
> Run 13: OK [0.680 secs, 22620 KB]
【CODE】
/*
ID:jie22221
TASK:cowpol
LANG:C++
*/
#include #include #include #include #define clr(a) memset((a),(0),sizeof(a))
using namespace std;
const int maxn=200005;
struct edge{int y;edge *next;};
int n,k;
int ans[maxn],belong[maxn],d[maxn],mdp[maxn],f[maxn];
bool v[maxn];

struct Link_t{
edge *ls[maxn];
void add(int x,int y){
edge *t=(edge*)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}
}G,Q;

void init(){
clr(G.ls);
clr(Q.ls);
clr(d);
clr(mdp);
clr(v);
clr(ans);
scanf("%d%d",&n,&k);
for (int x,i=1;i<=n;i++){
scanf("%d%d",&belong[i],&x);
G.add(x,i);
G.add(i,x);
}
}

void dfs(int p,int fa){
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa){
d[t->y]=d[p]+1;
dfs(t->y,p);
}
}

void make_Q(){
for (int i=1;i<=n;i++)
if (!mdp[belong[i]] || d[i]>d[mdp[belong[i]]])
mdp[belong[i]]=i;
for (int i=1;i<=n;i++)
if (mdp[belong[i]]!=i){
Q.add(i,mdp[belong[i]]);
Q.add(mdp[belong[i]],i);
}
}

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

void solve(int p,int fa){
f[p]=p;
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa)
solve(t->y,p);
v[p]=true;
for (edge *t=Q.ls[p];t;t=t->next)
if (v[t->y])
ans[belong[p]]=max(ans[belong[p]],d[t->y]+d[p]-2*d[gf(t->y)]);
f[p]=fa;
}

int main(){
freopen("cowpol.in","r",stdin);
freopen("cowpol.out","w",stdout);
init();
dfs(1,0);
make_Q();
solve(1,0);
for (int i=1;i<=k;i++)
printf("%dn",ans[i]);
}

【题目链接】http://ace.delos.com/ioiupload?init=1&a=CKerK76g6Pn
or 八中
【题目大意】
给定以1为根的一棵树。点数<=10^5
然后每个点按输入顺序被染色。
每次染色前都输出，从根到该结点的路径上，有多少个点被染色过了？
【算法分析】
首先，假如一个点染色，会影响到哪些点呢？
没错，就是以他为根的子树上的所有点。
所以我们按DFS序遍历的话，会得出一张线性表，在这个表上，每一个点为根的子树就会连在一起~
进而可以用线段树或者树状数组解决。
当然，树状数组好些多了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:slowdown
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int y;edge *next;}*ls[N];
int n,times;
int St[N],Ed[N],w[N];

void addedge(int x,int y){
edge *t=(edge *)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}

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

void dfs(int p,int fa){
St[p]=++times;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa)
dfs(t->y,p);
Ed[p]=times;
}

int Get_Sum(int p){
int res=0;
for (int i=p;i;i-=i&-i)
res+=w[i];
return res;
}

void Add(int p,int x){
for (int i=p;i<=n;i+=i&-i)
w[i]+=x;
}

void solve(){
memset(w,0,sizeof(w));
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
printf("%dn",Get_Sum(St[x]));
Add(St[x],1);
Add(Ed[x]+1,-1);
}
}

int main(){
freopen("slowdown.in","r",stdin);
freopen("slowdown.out","w",stdout);
init();
dfs(1,0);
solve();
return 0;
}