February 20, 2013 Graph Theory No comments Graph Theory
The Ghost Blows Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1017 Accepted Submission(s): 303
Problem Description
My name is Hu Bayi, robing an ancient tomb in Tibet. The tomb consists of N rooms (numbered from 1 to N) wh[……]
February 20, 2013 Graph Theory No comments Graph Theory
Forming Teams
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
One day n students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.
We[……]
February 20, 2013 Graph Theory No comments Graph Theory
As long as Binbin loves Sangsang
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 753 Accepted Submission(s): 195
Problem Description
Binbin misses Sangsang so much. He wants to meet with Sangsang as soon as possible.
Now Binbin dow[……]
February 20, 2013 Graph Theory No comments Graph Theory
PartyTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatus
Description
n12n 2n
Input
n n (n
February 20, 2013 Graph Theory No comments Graph Theory
Triangle LOVE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1462 Accepted Submission(s): 615
Problem Description
Recently, scientists find that there is love between any of two people. For example, between A and B, if A dont love[……]
February 20, 2013 Graph Theory No comments Graph Theory
note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.
///1
2-SATn2nn
x~xab(a,b)a,ba!=b,a!=~b (a,~b),(b,~a)2-SATx~xx~x
a=b(a,~a)a~a a=~b(a,a),(b,b)(a,~b)(b,~a) 2-SAT2-SAT(a,~b)(b,~a)2-SATa(~a,a)2-SAT
/[……]
February 20, 2013 Graph Theory No comments Graph Theory
Network
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 6744 Accepted: 3158
Description
A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The[……]
February 19, 2013 Graph Theory No comments Graph Theory
Time Limit:2000MS
February 19, 2013 Graph Theory No comments Graph Theory
1.
2.
3.
4.()
5.
6.
7.
<>kk-1
8.11G
Tarjan
1.
Tarjandfnlow
low[u]:=min(low[u],dfn[v])(u,v)vu
low[u]:=min(low[u],low[v])(u,v)vu
low[v]>=dfn[u],uvuvuuuuvvuuuv
1 2 3 4 5 6 7 8 9 10 11 12 13 | void tarjan(int x) { v[x]=1,dfn[x]=low[x]=++num; for(int i=head[x];i;i=next[i]) if(!v[ver[i]]) { tarjan(ver[i]); low[x]=min(low[x],low[ver[i]]); if(dfn[x]<=low[ver[i]]) v[x]++; } else low[x]=min(low[x],dfn[ver[i]]); if((x==1&&v[x]>2)||(x>1&&v[x]>1)) v[x]=2; else v[x]=1;//v[x]=2 } |
low[v]>dfn[u],(u,v) (u,v)vdfn[u][……]
February 19, 2013 Graph Theory No comments Graph Theory
note: This article comes from http://www.byvoid.com/blog/scc-tarjan/. Please contact me via lethic@163.com if there is any infringement.
http://www.byvoid.com/blog/scc-tarjan/ lethic@163.com.
G(strongly connected)GG(strongly connected components)
{1,2,3,4}1,2,3,4{5},{6}
O(N^2+M)Kos[……]
February 19, 2013 Graph Theory 1 comment Graph Theory
Invitation Cards
Time Limit:8000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
SubmitStatus
Description
In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all,[……]
February 19, 2013 Graph Theory No comments Graph Theory
Arbitrage
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
SubmitStatus
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar[……]
February 19, 2013 Graph Theory No comments Graph Theory
E – Wormholes
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
SubmitStatus
Description
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destin[……]
February 19, 2013 Graph Theory No comments Graph Theory
The Unique MST
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 14402 Accepted: 4981
Description
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tre[……]
note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.
GTGTGG
URAL1416M124750
T(-E1, +E2)TE1E2E2TGG(E2 – E1)GGE2V1V2E1V1V2
TG
1Prim
FF[x][y]TxyFPrim(i, j)ji=c[j]kijF[k][j]=max{F[k][i], (i, j)}FF[j][k]=F[k][j]G(i, j[……]
February 9, 2013 My Music No comments Guitar
February 9, 2013 My Music No comments Guitar
This is the first time I record a song with guitar playing.
Love will keep us alive is from the Eagles, which is very very famous.
I practiced for a whole month. And I spend a whole night finishing it in the basement under my apartment.
Love will keep us alive – Lethic.mp3
February 9, 2013 My Music No comments cover
February 9, 2013 MCU No comments MCU
This my MCU project for my MCU course last term. I spend a lot of time on it and I like it because it is simple but cool.
The CPU is MC89S51. It is an automatic speed control and alarm system based on the ultrasonic ranging. Since it can display the distance on the LCD screen, I call it Range Fin[……]
