之前做的两发
https://vjudge.net/problem/UVALive-3211
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = ;
int t[maxn][], n, tot, S[maxn*], scnt;
bool mark[maxn*];
struct Edge{
int v, nxt;
Edge(){}
Edge(int v, int nxt):v(v), nxt(nxt){}
}edge[maxn*maxn*];
int head[maxn*];
void addedge(int u, int v){
edge[tot] = Edge(v, head[u]);
head[u] = tot++;
}
void conj(int x, int detx, int y, int dety){
x = *x+detx;
y = *y+dety;
addedge(x^, y);
addedge(y^, x);
}
void build(int mid){
tot = ;
memset(head, -, sizeof head);
for(int i = ; i < n; i++)
for(int a = ; a < ; a++)
for(int j = i+; j < n; j++)
for(int b = ; b < ; b++)
if(fabs(t[i][a]-t[j][b]) < mid)
conj(i, a^, j, b^); }
bool dfs(int x){
if(mark[x])
return true;
if(mark[x^])
return false;
mark[x] = true;
S[scnt++] = x;
for(int i = head[x]; ~i; i = edge[i].nxt){
int v = edge[i].v;
if(!dfs(v))
return false;
}
return true;
}
bool solve(){
memset(mark, false, sizeof mark);
for(int i = ; i < *n; i+=){
if(!mark[i]&&!mark[i+]){
scnt = ;
if(!dfs(i)){
for(int j = ; j < scnt; j++){
mark[S[j]] = false;
}
scnt = ;
if(!dfs(i+))
return false;
}
}
}
return true;
}
int main(){
while(scanf("%d", &n)== && n){
for(int i = ; i < n; i++)
for(int j = ; j < ; j++){
scanf("%d", &t[i][j]);
}
int l = , r = 1e7;
while(l < r){
int mid = (r-l+)/+l;
build(mid);
if(solve())
l = mid;
else
r = mid-;
}
printf("%d\n", l);
}
return ;
}
/*
10
44 156
153 182
48 109
160 201
55 186
54 207
55 165
17 58
132 160
87 197
*/
https://vjudge.net/problem/UVALive-3713
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = ;
int age[maxn], n, m, tot, S[maxn*], scnt;
double ave;
bool mark[maxn*];
struct Edge{
int v, nxt;
Edge(){}
Edge(int v, int nxt):v(v), nxt(nxt){}
}edge[*];
int head[maxn*];
void addedge(int u, int v){
edge[tot] = Edge(v, head[u]);
head[u] = tot++;
}
void conj(int x, int detx, int y, int dety){
x = *x+detx;
y = *y+dety;
addedge(x^, y);
addedge(y^, x);
}
bool dfs(int x){
if(mark[x])
return true;
if(mark[x^])
return false;
mark[x] = true;
S[scnt++] = x;
for(int i = head[x]; ~i; i = edge[i].nxt){
int v = edge[i].v;
if(!dfs(v))
return false;
}
return true;
}
bool solve(){
memset(mark, false, sizeof mark);
for(int i = ; i < *n; i+=){
if(!mark[i]&&!mark[i+]){
scnt = ;
if(!dfs(i)){
for(int j = ; j < scnt; j++){
mark[S[j]] = false;
}
scnt = ;
if(!dfs(i+))
return false;
}
}
}
return true;
}
int main(){
while(scanf("%d%d", &n, &m)){
tot = ;
memset(head, -, sizeof head);
if(!n&&!m)
break;
double sum = ;
for(int i = ; i < n; i++){
scanf("%d", &age[i]);
sum += age[i];
}
ave = sum/n;
while(m--){
int u, v;
scanf("%d%d", &u, &v);
u--;
v--;
if((age[u]<ave&&age[v]<ave) || (age[u]>=ave&&age[v]>=ave)){
conj(u, , v, );
conj(u, , v, );
}
else{
conj(u, , v, );
}
}
if(!solve()){
puts("No solution.");
}
else{
for(int i = ; i < *n; i+=){
if(mark[i]){
printf("C\n");
}
else{
if(age[i/]>=ave)
printf("A\n");
else
printf("B\n");
}
}
}
}
return ;
}
/*
16 20 21
22
23
24
25
26
27
28 101 102 103 104 105 106 107 108
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16 1 10 2 9
3 12 4 11 5 14 6 13 7 16 8 15 1 12 1 13 3 16 6 15 0 0*/
由于拆点，点数应该是2n...
每个字句a|b 加边!a -> b, !b -> a， 两条边呢...
点和边开的不够大，一言不合就爆掉了...