求提高组第三题二分法详解 - noip吧

level 5

折わた翼楼主

RT

2010年11月22日 03点11分 1

level 1

timtopcoder

二分了把所有大于二分值的边都拿出来，看下用这些边能不能构成二分图就行了

2010年11月22日 03点11分 2

level 5

折わた翼楼主

NOIP我都是自学的= =...
指导老师相当于空气般的存在= =
关于二分的资料没看过~
详细点~~谢

2010年11月22日 03点11分 3

level 5

折わた翼楼主

诶.
看起来不管二分还是并查都是预排序再写程序比较方便诶
难怪某牛说不会快排就别来NOIP了= =

2010年11月22日 04点11分 4

level 5

折わた翼楼主

对了.顺便问下这题用并查的话应该怎么设计数据结构...
我开的数组爆了...

2010年11月22日 05点11分 5

level 5

折わた翼楼主

排序链表怎么样

2010年11月22日 05点11分 6

level 1

timtopcoder

回复：6楼
什么叫排序链表= =。前向星？。。
直接把起点相同的边链起来就行了= =。名字各个地方叫的都不一样。。我们这叫“边表”。。

2010年11月22日 07点11分 7

level 5

折わた翼楼主

...都是浮云.有一个20k*20k的数组搞定.....
用链表做太麻烦了...检查一个点就要遍历一次...

2010年11月22日 07点11分 8

level 5

折わた翼楼主

下午闲的蛋疼...前3道题AC了..第4题明天再重写吧...
哎哎哎

2010年11月22日 07点11分 9

level 1

timtopcoder

回复：8楼
???
显然链表写起来非常简单啊。。
你2W*2W的数组开的下么。。1.5G了。。

2010年11月22日 07点11分 10

level 5

折わた翼楼主

我开2个100k 的开爆了.
20k*20k的没出错诶

2010年11月22日 08点11分 11

level 5

折わた翼楼主

关键链表的遍历太麻烦太麻烦了吧- -

2010年11月22日 08点11分 12

level 1

timtopcoder

回复：12楼
你肯定想囧了。。应该非＜虻サ摹！Ｎ乙恢倍荚谟谩！<br>给你写个。。。
-----------------------------------------
// structures and functions
int begin[MAXNODE + 1], end[MAXEDGE + 1], next[MAXEDGE + 1];
int Count = 0;
void AddEdge(int a, int b)
{
     Count ++;
     next[Count] = begin[a];
     begin[a] = Count;
     end[Count] = b;
}
-----------------------------------
// add edges
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; i ++)
{
     scanf("%d%d", &a, &b);
     AddEdge(a, b);
}
----------------------------------
// usage
void dfs(int x)
{
     hash[x] = true;
     for (int now = begin[x]; now; now = next[now])
         if (!hash[end[now]])
             dfs(end[now]);
}

2010年11月22日 09点11分 13

level 5

折わた翼楼主

鄙人P党...
20k*20k的数组用并查解的
本机测了几组数据.没问题
program prison;
var f:array[1..20000,1..20000] of longint;
     n,m,i,j,k,max,max1,maxi,maxj:integer;
     t:boolean;
procedure recor(x,y:integer);
begin
   maxi:=x;
   maxj:=y;
   max1:=abs(f[x,y]);
end;
procedure mark(x,y,z:integer);
begin
   if f[y,x]<f[z,x] then f[y,x]:=-f[y,x] else f[z,x]:=-f[z,x];
end;
procedure mark1(x,y,z:integer);
begin
   if f[x,y]<f[x,z] then f[x,y]:=-f[x,y] else f[x,z]:=-f[x,z];
end;
function min(w,x,y,z:integer):longint;
begin
   min:=f[w,y];
   if min<f[w,z] then min:=f[w,z];
   if min<f[x,y] then min:=f[x,y];
   if min<f[x,z] then min:=f[x,z];
end;
function min1(w,x,y,z:integer):longint;
begin
   min1:=f[w,x];
   if min1<f[w,y] then min1:=f[w,y];
   if min1<f[x,z] then min1:=f[x,z];
   if min1<f[y,x] then min1:=f[y,z];
end;
begin
   readln(n,m);
   for i:=1 to m do
     begin
       read(j,k);
       readln(f[j,k]);
     end;
   repeat
     max1:=0;
     t:=true;
     for i:=1 to n do
       for j:=i+1 to n do
         begin
           if max1<abs(f[i,j]) then recor(i,j);
           if f[i,j]>0 then t:=false;
         end;
     if f[maxi,maxj]<0 then max1:=f[maxi,maxj] else f[maxi,maxj]:=0;
     for i:=maxj+1 to n do
       begin
         if (f[maxi,i]>0) and (f[maxj,i]>0) then mark(i,maxi,maxj);
         for j:=i+1 to n do
           if (f[i,j]>0) and (f[i,j]<min(maxi,maxj,i,j)) then f[i,j]:=-f[i,j];
       end;
     for i:=1 to maxi-1 do
       begin
         if (f[i,maxi]>0) and (f[i,maxj]>0) then mark1(i,maxi,maxj);
         for j:=1 to i+1 do
           if (f[i,j]>0) and (f[i,j]<min(i,j,maxi,maxj)) then f[i,j]:=-f[i,j];
       end;
     for i:=maxi+1 to maxj-1 do
      for j:=maxi+1 to maxj-1 do
        if (f[i,j]>0) and (f[i,j]<min(maxi,i,j,maxj)) then f[i,j]:=-f[i,j];
   until (max1<0) or t;
   if t then write(0) else write(abs(max1));
end.

2010年11月22日 09点11分 14

level 5

折わた翼楼主

主程序其实就不到10行..
其他的都是判冲突做标记...

2010年11月22日 09点11分 15