[POJ 3683] 2-SAT、输出方案

【题目大意】给定N个区间（A，B），和长度len，让你对于每一组区间在(A,A+len)和(B-len,B)这两个区间中选一个，使得选取的区间交集为空集

【算法分析】典型的2-SAT，要注意一下输出方案必须按反拓扑序输出。

【其它】贡献2WA。del过程一开始没写好，应先把图倒置。

【CODE】

#include

[SGU 212]层次图的网络流、预流推进+sap**

【题目大意】 N个点M条边，每个点的距离标号已给出，且I阶段的点只向I+1阶段的点连边，求最大流。

【算法分析】本来以为是直接sap秒杀。。。因为见惯了这sap的暴力。。。但是做了这题以后，我终于知道了一件事，sap不是万能的，没有sap却是万万不能的。。。
这个比较囧。一开始以为水题，直接sap，10分钟交上去，TLE AT 17
然后就各种囧，加了个优化，就是预处理sap的d数组，依然飘逸地TLE
然后我就是开始想HLPP，但是用不习惯，不爽。。。
然后我就想，能不能把sap和预流推进搞到一起去呢？
于是就诞生了今天我写的这个东东。。。
下面进入正题：
其实说来也简单，因为是层次图，所以我就先从S点开始bfs地向后推进一次，然后在根据上一次bfs的list把上一次推进不能到达T的盈余推回到S来，然后就可以初始了一个流出来
最后再用bfs预处理sap的标号，最后用我们可爱的sap把它解决了。。。

【其它】重写以后1A
994533 02.02.10 17:37 edward 212 .CPP Accepted 1412 ms 15643 kb 这个比较激动。。。看着比较少人A，加上经历了艰难困苦以后终于AC，yeah一个
【CODE】
#include #include #include #define N 1555
#define E 666666
//#define N 100
//#define E 200
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,op,c;}g[E];
int n,edge,L,S,T;
int e[N],fa[N],ls[N],cur[N],d[N],num[N],list[N],C[E],v[N];

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

void init(){
int m,x,y,c;
scanf("%d%d%d",&n,&m,&L);
for (int i=1;i<=n;i++){
scanf("%d",&x);
if (x==1) S=i;
if (x==L) T=i;
}   
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
C[edge]=c;
C[edge-1]=c;
}   
}

void first_push(){
list[1]=S; e[S]=inf; v[S]=1;
int head=0,tail=1,nf;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if ((t&1) && g[t].c){
nf=g[t].c; if (e[list[head]]e[g[t].x]-=nf;
e[g[t].y]+=nf;
g[t].c-=nf;
if (nf && !v[g[t].y]){
tail++;
list[tail]=g[t].y;
v[g[t].y]=1;
}   
}   
}
// push back
for (int i=tail-1;i>=1;i–){
for (int t=ls[list[i]];t;t=g[t].next)
if (!(t&1) && (C[g[t].op]-g[g[t].op].c)){
nf=C[g[t].op]-g[g[t].op].c; if (e[list[i]]e[g[t].x]-=nf;
e[g[t].y]+=nf;
g[g[t].op].c+=nf;
}   
}   
}

void prebfs(){
for (int i=1;i<=n;i++) d[i]=inf;
list[1]=T; d[T]=0;
int head=0,tail=1;
while (head!=tail){
head++;
for (int t=ls[list[head]];t;t=g[t].next)
if (!(t&1) && g[g[t].op].c && d[g[t].y]==inf){
d[g[t].y]=d[g[t].x]+1;
tail++;
list[tail]=g[t].y;
}
}   
}

void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t;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]].cfor (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}   
}       

void sap(){
for (int i=1;i<=n;i++){
num[d[i]]++;
cur[i]=ls[i];
}   
int i=S;
while (d[S]for (;cur[i];cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
num[d[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;
}   
}   
}   
}   

void print(){
for (int i=1;iprintf("%dn",C[i]-g[i].c);
}   

int main(){
init();
first_push();
prebfs();
sap();
print();
}   

[SGU 210]最大匹配、贪心**

【题目大意】 N个男的、N个女的（N<=400），互相匹配。每个男的有权值，求最后权值最大。 【算法分析】将男的按权值排序，然后根据这个顺序来最大匹配。匈牙利算法每次寻找交错轨的话，前面已匹配的节点绝不会再丢失匹配，所以根据这个性质，可以这么做。 【其它】SGU跑了近10分钟给了我一个CE。。。#include 994478 02.02.10 16:06 edward 210 .CPP Accepted 559 ms 2499 kb
【CODE】
#include #include #include #include using namespace std;
struct edge{int y; edge *next;};
struct data{int w,mark;}d[411];
int n,link[411],cover[411],ans[411];
edge *ls[411];
bool cmp(data x,data y){return x.w>y.w;}

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

bool dfs(int k){
for (edge *t=ls[k];t;t=t->next)
if (!cover[t->y]){
cover[t->y]=1;
int q=link[t->y];
link[t->y]=k;
if (q==0 || dfs(q)) return true;
link[t->y]=q;
}   
return false;
}   

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
ls[i]=NULL;
scanf("%d",&d[i].w);
d[i].mark=i;
}
for (int i=1;i<=n;i++){
int num,x;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&x);
add(i,x);
}   
}   
sort(&d[1],&d[n+1],cmp);
for (int now=1;now<=n;now++){
memset(cover,0,sizeof(cover));
dfs(d[now].mark);
}
for (int i=1;i<=n;i++)
if (link[i]) ans[link[i]]=i;
for (int i=1;iprintf("%dn",ans[n]);
}   

[SGU138]构造法**

【题目大意】 有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");
}
}