作者存档：edward_mj

【题目大意】给定一个无向图，让你求最小去掉多少个点以后使得原图不连通。

【算法分析】如果是有源汇的话就简单了，直接拆点然后求最小割就可以。于是这题就枚举源汇求最小割就行了。

【其它】1A
6393220 edward2 1966 Accepted 396K 125MS G++ 2212B 2010-01-31 18:25:01
【CODE】
#include #include #include #define inf 200
struct gtp{int x,y,next,c,op;}g[10000];
int n,m,e,a[50][50],S,T,flow;
int ls[100],cur[100],fa[100],d[100],num[100];

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

void change(){
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;
}
flow+=nf;
}

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

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; 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].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

int main(){
while (scanf("%d%d",&n,&m)!=EOF){
memset(a,0,sizeof(a));
for (int i=1;i<=m;i++){
int x,y;
scanf(" (%d,%d)",&x,&y);
a[x][y]=1; a[y][x]=1;
}
int ans=inf;
for (S=n;S<2*n;S++)
for (T=0;T if (S-n!=T){
e=0;
memset(ls,0,sizeof(ls));
for (int i=0;i for (int j=0;j if (a[i][j]) addedge(i+n,j,inf);
for (int i=0;i sap();
if (flow }
if (ans>n) ans=n;
printf("%dn",ans);
}
return 0;
}

【题目大意】给你N个点，源点和汇点，然后给定一个邻接矩阵，让你求从源到汇的一个字典序最小的点割集。

【算法分析】一个点拆成两个点，图中的边设成0x7FFFFFFF，然后一个点管出度，一个点管入度。然后就变成了求这个网络的最小割。由于题目要求字典序最小，所以必须枚举删点。

【其他】WA了1次，因为NO ANSWER的其中一个情况漏掉了。
6390962 edward2 1815 Accepted 864K 579MS G++ 2568B 2010-01-30 23:22:14
【CODE】
#include #include #include #define E 100000
#define N 401
struct edge{int x,y,op,c,next;}g[E];
int n,S,T,e,a[N][N];
int fa[N],cur[N],num[N],d[N],ls[N],v[N];

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

int 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[g[fa[i]].op].c+=nf;
}
return nf;
}

int sap(){
int FF=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=1;i<=2*n;i++) cur[i]=ls[i];
num[0]=2*n;
int i=S;
while (d[S]<2*n){
for (;cur[i]!=0;cur[i]=g[cur[i]].next)
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
if (cur[i]==0){
if (–num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
FF+=change();
i=S;
}
}
}
return FF;
}

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; 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].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

void init(){
memset(v,0,sizeof(v));
scanf("%d%d%d",&n,&S,&T);
S+=n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}

void work(){
if (S-n==T || a[S-n][T]==1){
printf("NO ANSWER!n");
return;
}
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++) addedge(i,i+n,1);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a[i][j]) addedge(i+n,j,0x7FFFFFFF);
int flow=sap();
printf("%dn",flow);
for (int i=1;i<=n;i++){
if (flow==0) break;
v[i]=1;
e=0; memset(ls,0,sizeof(ls));
for (int j=1;j<=n;j++)
if (v[j]==0) addedge(j,j+n,1);
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
if (a[j][k]) addedge(j+n,k,0x7FFFFFFF);
int tf=sap();
if (tf else v[i]=0;
}
for (int i=1;i<=n;i++)
if (v[i]) printf("%d ",i);
}

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

【题目大意】给定一个混合图（有无向边也有有向边），问图中是否存在欧拉回路。另外该题保证存在一个顶点，使得其他顶点都能到达。即保证的连通性，我们只需要考虑度的限制就可以了。

【算法分析】对于有向边，度是不可改变的。只有无向边可以变换方向。
我们先把无向边任意地定一个方向。
1、如果有边的总度数为奇数，那么肯定不存在欧拉回路。
2、对于出度大于入度的点连边[S,i]，c=-du[i]/2。du为入度-出度。
对于入度大于出度的点连边[i,T]，c=du[i]/2。
然后把无向边都按你定的方向加入图中，容量都为1。
进行最大流。
如果最后与源或汇相连的边都是满流，则符合条件。
————————————————————————————————————————————
为什么要这样呢？
我们可以想象，最大流流过那条边，相当于把这条边反向，而如果要让du[i]变为0，那么必须反向du[i]/2条边。所以源汇相连的边容量为du[i]/2。然后中间的可以看成一个二分图，模拟一下就会知道是什么意思。

【其它】 6389700 edward2 1637 Accepted 420K 0MS G++ 2796B 2010-01-30 18:36:51 排得挺靠前啊。。。虽然都是0MS，ORZ

【CODE】
#include #include #include #define N 202
#define Ed 20001
struct gtp{int x,y,c,op,next;}g[Ed];
struct gtp2{int x,y,next;}G[Ed];
int n,e,m,E;
int du[N],wxn[N],ls[N],LS[N];
int fa[N],cur[N],num[N],d[N];

void addEdge(int x,int y){
E++;
G[E].x=x; G[E].y=y; G[E].next=LS[x]; LS[x]=E;
}

void init(){
E=0;
memset(du,0,sizeof(du));
memset(wxn,0,sizeof(wxn));
memset(LS,0,sizeof(LS));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y,q;
scanf("%d%d%d",&x,&y,&q);
if (q==1){
du[x]–;
du[y]++;
}
else{
addEdge(x,y);
du[x]–;
du[y]++;
}
}
}

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

void build(){
e=0;
memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++){
if (du[i]<0) addedge(0,i,-du[i]/2);
if (du[i]>0) addedge(i,n+1,du[i]/2);
for (int t=LS[i];t!=0;t=G[t].next)
addedge(G[t].x,G[t].y,1);
}
}

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

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;
}
}

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

bool flag(){
for (int i=1;i<=n;i++)
if (du[i]%2!=0) return false;
for (int i=1;i<=n;i++)
for (int t=ls[i];t!=0;t=g[t].next)
if ((t&1) && (g[t].x==0 || g[t].y==n+1) && g[t].c!=0) return false;
return true;
}

int main(){
int tc;
scanf("%d",&tc);
for (int i=0;i init();
build();
sap();
if (flag()) printf("possiblen");
else printf("impossiblen");
}
return 0;
}

【题目大意】给定一个无向图，让你求两条从1到N的最短路，使得它们没用重复的边。

【算法分析】先dijkstra，然后如果d[i]+a[i][j]==d[j]的话连边[i,j]（流量为1），然后求最大流，如果流量<2的话，就是无解，否则从源点dfs到汇点两次（顺着有流量的边，经过的就标记），输出路径即可。 【其它】这题空间卡得很紧。。。搞了几次才过。 【CODE】
#include #include #include #define N 401
#define E 160001
struct gtp{int x,y,op,next,c;}g[E];
int n,m,e,a[N][N];
int ls[N],cur[N],fa[N],num[N],d[N],v[N];
int flow;

void init(){
memset(a,60,sizeof(a));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if (wa[x][y]=w;
a[y][x]=w;
}   
}
m*=2;   
}   

void dijkstra(){
memset(v,0,sizeof(v));
for (int i=2;i<=n;i++) d[i]=a[1][i];
d[1]=0; v[1]=1;
for (;;){
int mm=a[0][0],j;
for (int i=1;i<=n;i++)
if (v[i]==0 && d[i]mm=d[i];
j=i;
}
if (mm==a[0][0]) break;
v[j]=1;
for (int i=1;i<=n;i++)
if (d[j]+a[j][i]}   
}   

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; 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].op=e-1; g[e].next=ls[y]; ls[y]=e;
}   

void build(){
e=0;
memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j && d[i]+a[i][j]==d[j]) addedge(i,j,1);
}   

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

void change(){
flow++;
for (int i=n;i!=1;i=g[fa[i]].x){
g[fa[i]].c–;
g[g[fa[i]].op].c++;
}   
}   

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

bool dfs(int k){
if (k==n){
printf("%dn",n);
return true;
}
printf("%d ",k);
for (int t=ls[k];t!=0;t=g[t].next)
if ((t&1) && g[t].c==0){
g[t].c=-1;
if (dfs(g[t].y)) return true;
}
return false;
}   

int main(){
init();
dijkstra();
build();
sap();
if (flow<2) printf("No solutionn");
else{
dfs(1);
dfs(1);
}
return 0;
}   

【题目大意】给定N只牛，B个牛棚，还有每只牛给这个牛棚的打分，并且每只牛棚只能装suffer[i]只牛，让你求一个最小的分数区间[A,B]，使得每只牛都能放进牛棚。

【算法分析】枚举答案，然后枚举其实分数，然后用网络流判定就行了。

还有一种做法是根据单调性，用双指针维护，相当于维护一个队列。这样会快一点，但是我写了一次，莫名其妙的TLE和WA，于是只能用这种方法。

【其它】

6376444 edward2 3189 Accepted 1320K 188MS G++ 2456B

2010-01-27 11:05:43

还算比较快

【CODE】

#include