分类存档：默认分类

【题目链接】http://acm.hust.edu.cn/thanks/problem.php?id=1017

【题目大意】

给定一个M*N的矩阵，上面只有1和0。其中M,N<=1000。

并且每一行的1的数量<=100。

让你取一些行，使得每一列恰好有一个1。

【算法分析】

这个吓人的规模。。。没错。。。就是搜索。

Dancing Link + Algorithm X

【其它】

很寂寞。时限15秒，我跑了4秒。第一名跑了120+MS。。。很好很沙茶。

【CODE】

C++ CODE   :Hust1017 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105 #include #include #include const int N=1005;
int m,n,dep,tot;
int Sum[N];
int L[N],R[N],U[N][N],D[N][N];
int a[N][105];
int ansL[N];
int Sx[N*N/10],Sy[N*N/10];

void init(){
int i,j,x;
for (j=0;j<=n;j++){
D[0][j]=0;
U[0][j]=0;
}
memset(Sum,0,sizeof(Sum));
for (i=1;i<=m;i++){
scanf("%d",&a[i][0]);
for (j=1;j<=a[i][0];j++){
scanf("%d",&x);
a[i][j]=x;
Sum[x]++;
D[i][x]=0;
U[i][x]=U[0][x];
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
}
}
for (i=0;i for (i=1;i<=n;i++) L[i]=i-1; L[0]=n;
}

void Delete(int Col){
int i,j,tmp=tot,next;
for (i=D[0][Col];i;i=next){
next=D[i][Col];
for (j=1;j<=a[i][0];j++){
int &x=a[i][j];
Sum[x]–;
U[D[i][x]][x]=U[i][x];
D[U[i][x]][x]=D[i][x];
tot++;
Sx[tot]=i;
Sy[tot]=x;
}
}
L[R[Col]]=L[Col];
R[L[Col]]=R[Col];
}

void Recover(int k){
while (tot!=k){
int &i=Sx[tot],&x=Sy[tot];
Sum[x]++;
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
tot–;
}
}

bool dfs(){
if (!R[0]) return true;
int i,j,Min=0x7FFFFFFF,Mini,tmp;
for (i=R[0];i;i=R[i])
if (Sum[i] Min=Sum[i];
Mini=i;
}
if (Min==0) return false;
for (i=D[0][Mini];i;i=D[i][Mini]){
ansL[dep++]=i;
tmp=tot;
for (j=1;j<=a[i][0];j++)
Delete (a[i][j]);
if (dfs()) return true;
dep–;
for (j=a[i][0];j>=1;j–){
int &Col=a[i][j];
L[R[Col]]=Col;
R[L[Col]]=Col;
}
Recover(tmp);
}
return false;
}

void output(){
printf("%d",dep-1);
for (int i=1;i puts("");
}

int main(){
while (1){
if (scanf("%d%d",&m,&n)==EOF) break;
init();
dep=1;
tot=0;
if (dfs()) output();
else puts("NO");
}
return 0;
}

昨晚的模拟赛下面交400分的程序被测成0分。
貌似好多神牛都这么悲剧。。。。
真是疼。。。
我从昨晚深夜观察，发现几次rejudge我的评测结果有如下变化：
第一次：
第 1 题: NetworkError
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.IO.MemoryStream.set_Capacity(Int32 value)
在 System.IO.MemoryStream.EnsureCapacity(Int32 value)
在 System.IO.MemoryStream.Write(Byte[] buffer, Int32 offset, Int32 count)
在 System.IO.BinaryWriter.Write(String value)
在 VijosNT_Server.TestCase.Serialize(BinaryWriter Writer)
在 VijosNT_Server.TestCaseLoader.Write(IList`1 TestCaseList, BinaryWriter Writer)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
第二次：
第 1 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
第三次：
第 1 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: Accepted
VijosNT Judger: 1.2 build 100318
Judger #2
Compiler: G++111
g++ -O2 -g -otest.exe test.cpp
Test #1: Accepted… 0ms
Test #2: Accepted… 0ms
Test #3: Accepted… 0ms
Test #4: Accepted… 0ms
Test #5: Accepted… 0ms
Test #6: Accepted… 0ms
Test #7: Accepted… 0ms
Test #8: Accepted… 0ms
Test #9: Accepted… 0ms
Test #10: Accepted… 0ms
Total score: 100, time usage: 0ms
第 4 题: Accepted
VijosNT Judger: 1.2 build 100318
Judger #2
Compiler: G++111
g++ -O2 -g -otest.exe test.cpp
Test #1: Accepted… 0ms
Test #2: Accepted… 0ms
Test #3: Accepted… 0ms
Test #4: Accepted… 46ms
Test #5: Accepted… 46ms
Test #6: Accepted… 140ms
Test #7: Accepted… 78ms
Test #8: Accepted… 62ms
Test #9: Accepted… 250ms
Test #10: Accepted… 265ms
Total score: 100, time usage: 887ms
、
、
、
、
、
、
第四次：
变回第二次一样。
、
、
、
、
、
、
第五次：
第 1 题: InternalError
未将对象引用设置到对象的实例。
第 2 题: InternalError
未将对象引用设置到对象的实例。
第 3 题: InternalError
未将对象引用设置到对象的实例。
第 4 题: InternalError
未将对象引用设置到对象的实例。
、
、
、
、
、
、
最后&&现在：
第 1 题: NetworkError
第 2 题: NetworkError
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
弱问400->0_RP能+多少？
更疼的是我的徒弟多次rejudge依然屹立290分。排行第3的淫霸地位= =。。。
真真无语也~