把凸包上的点按水平垂直排序，输出时要注意，从最左下方的点开始按逆时针方向输出。
uva 11624
2009年9月17日 08:00
直接用bfs做。
代码：
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define FR(i,a,b) for(i=(a);i<(b);i++)
#define FOR(i,n) FR(i,0,n)
#define CLR(x,a) memset(x, a,sizeof(a))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ABS(a) ((a)<0?-(a):(a))
#define oo 0x7fffffff
#define MAXN 1002
#define MAXQ MAXN*MAXN
typedef long long int64;
char map[MAXN][MAXN];
int que[MAXQ][2];
int dis_j[MAXN][MAXN];
int dis_f[MAXN][MAXN];
int dis[MAXN][MAXN];
int pos[MAXN * 4][2];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int r, c;
int jx, jy;
int fx[MAXQ], fy[MAXQ];
int cnt, nf;
int head, tail;
void bfs(char ch)
{
int tx, ty, x, y, i, j;
memset(dis, -1, sizeof(dis));
head = 0; tail = 0;
if(ch == 'J')
{
que[tail][0] = jx; que[tail++][1] = jy;
dis[jx][jy] = 0;
}
else
{
FR(i, 1, nf+1)
{
x = fx[i]; y = fy[i];
dis[x][y] = 0;
que[tail][0] = x;
que[tail][1] = y;
tail++;
}
}
while(head < tail)
{
x = que[head][0]; y = que[head][1];
FOR(i, 4)
{
tx = x + dx[i]; ty = y + dy[i];
if(tx < 0 || tx > r || ty < 0 || ty > c) continue;
if(dis[tx][ty] != -1) continue;
if(map[tx][ty] == '#') continue;
if(map[tx][ty] == 'F') continue;
dis[tx][ty] = dis[x][y] + 1;
que[tail][0] = tx; que[tail][1] = ty;
tail++;
}
head++;
}
}
void init()
{
int i, j;
scanf("%d %d", &r, &c);
getchar();
cnt = 0; nf = 0;
FR(i, 1, r + 1)
{
FR(j, 1, c + 1)
{
map[i][j] = getchar();
if(map[i][j] == 'J') { jx = i; jy = j;}
if(map[i][j] == 'F') { nf++; fx[nf] = i; fy[nf] = j;}
if((i == 1 ||i == r || j == 1 || j == c) && map[i][j] != '#')
{
cnt++;
pos[cnt][0] = i;
pos[cnt][1] = j;
}
}
getchar();
}
}
void solve()
{
int min, i, j, x, y;
bfs('J');
memcpy(dis_j, dis, sizeof(dis));
bfs('F');
memcpy(dis_f, dis, sizeof(dis));
min = oo;
FR(i, 1, cnt + 1)
{
x = pos[i][0]; y = pos[i][1];
if((dis_j[x][y] != -1 && dis_j[x][y] < dis_f[x][y]) || (dis_j[x][y] != -1 && dis_f[x][y] == -1))
{
if(min > dis_j[x][y]) min = dis_j[x][y];
}
}
if(min == oo) printf("IMPOSSIBLE\n");
else printf("%d\n", min + 1);
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
init();
solve();
}
return 0;
}
pku 2987
2009年9月11日 18:14
题目其实是求最大闭合图，将原问题的图转化为最小割模型。
在原图点集合基础上添加源st和汇ed，将原图每条边(u, v)容量设为oo，增加源点st到原图每个正权点v的有向边，容量为node[v]，增加原图每个负权点到汇点ed的有向边，容量为-node[v]，然后求st到ed的最大流，在残留网络中与源点相连的点为被选择的点，所有正权点权值之和减去最大流为题中所求最大获益，题目权值的绝对值小于10000000，得用long long，呵呵，在这点上WA了一次。
代码：
#include <stdio.h>
#include <string.h>
#define oo 0x7fffffff
#define MAXM 100002
#define MAXN 5005
typedef long long int64;
typedef struct
{
int u; int v; int cap; int next;
}edge_t;
edge_t e[MAXM];
int first[MAXN];
int node[MAXN];
int dist[MAXN];
int now[MAXN];
int pre[MAXN];
int cnt[MAXN];
int cur[MAXN];
int tot, st, ed, n2, n;
int64 sum;
void add(int u, int v, int cap)
{
e[++tot].u = u; e[tot].v = v; e[tot].cap = cap; e[tot].next = first[u]; first[u] = tot;
e[++tot].u = v; e[tot].v = u; e[tot].cap = 0; e[tot].next = first[v]; first[v] = tot;
}
void init()
{
int i, j, m;
scanf("%d %d", &n, &m);
memset(first, -1, sizeof(first));
sum = 0; tot = -1; st = 0; ed = n + 1;
for(i = 1;i <= n; i++)
{
scanf("%d", &node[i]);
if(node[i] > 0) { add(st, i, node[i]); sum += node[i];}
else add(i, ed, -node[i]);
}
while(m--)
{
scanf("%d %d", &i, &j);
add(i, j, oo);
}
n2 = n; n += 2;
}
int64 sap()
{
int64 tot_flow;
int now_flow, found, min;
int i, j, t;
memset(dist, 0, sizeof(dist));
memset(now, -1, sizeof(now));
memset(cnt, 0, sizeof(cnt));
i = st;
tot_flow = 0; now_flow = oo;
cnt[0] = n;
while(dist[st] < n)
{
cur[i] = now_flow; found = 0;
if(now[i] == -1) t = first[i];
else t = now[i];
while(t != -1)
{
j = e[t].v;
if(e[t].cap > 0 && dist[j] + 1 == dist[i])
{
found = 1; now[i] = t;
if(e[t].cap < now_flow) now_flow = e[t].cap;
pre[j] = t; i = j;
if(i == ed)
{
tot_flow += now_flow;
while(i != st)
{
e[pre[i]].cap -= now_flow;
e[pre[i]^1].cap += now_flow;
i = e[pre[i]].u;
}
now_flow = oo;
}
break;
}
t = e[t].next;
}
if(found) continue;
if(--cnt[dist[i]] == 0) break;
min = n - 1;
t = first[i];
while(t != -1)
{
if(e[t].cap > 0 && dist[e[t].v] < min)
{
min = dist[e[t].v];
now[i] = t;
}
t = e[t].next;
}
dist[i] = min + 1;
cnt[dist[i]]++;
if(i != st)
{
i = e[pre[i]].u;
now_flow = cur[i];
}
}
return tot_flow;
}
void dfs(int u)
{
int t, v;
cnt[u] = 1;
t = first[u];
while(t != -1)
{
v = e[t].v;
if(e[t].cap > 0 && cnt[v] == 0) dfs(v);
t = e[t].next;
}
}
void solve()
{
int64 res;
int ans, i;
res = sap();
memset(cnt, 0, sizeof(cnt));
dfs(st); ans = 0;
for(i = 1;i <= n2; i++) ans += cnt[i];
printf("%d %lld\n", ans, sum - res);
}
int main()
{
init();
solve();
return 0;
}
pku 2289
2009年9月11日 17:19
思路：二分最大组的人数，建图，然后求最大流，sap实在强大，呵呵。
代码：
#include <stdio.h>
#include <string.h>
#define oo 0x7fffffff
#define MAXN 1508
typedef struct
{
int u; int v; int cap; int next;
}edge_t;
edge_t e[MAXN * MAXN];
char adj[1002][502];
int first[MAXN];
int dist[MAXN];
int now[MAXN];
int pre[MAXN];
int cnt[MAXN];
int cur[MAXN];
int in[502];
int tot, st, ed;
int n2, n, m;
void add(int u, int v, int cap)
{
e[++tot].u = u; e[tot].v = v; e[tot].cap = cap; e[tot].next = first[u]; first[u] = tot;
e[++tot].u = v; e[tot].v = u; e[tot].cap = 0; e[tot].next = first[v]; first[v] = tot;
}
int init()
{
char ch;
int i, j;
scanf("%d %d", &n, &m);
if(n == 0 && m == 0) return 0;
memset(adj, 0, sizeof(adj));
memset(in, 0, sizeof(in));
st = 0; ed = n + m + 1; n2 = n;
getchar();
for(i = 1;i <= n; i++)
{
ch = getchar();
while((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) ch = getchar();
while(ch == ' ') ch = getchar();
while(1)
{
j = 0;
while(ch >= '0' && ch <= '9')
{
j = j * 10 + ch - '0';
ch = getchar();
}
adj[i][j + 1] = 1;
in[j + 1]++;
if(ch == '\n') break;
while(ch == ' ') ch = getchar();
}
}
n = n + m + 2;
return 1;
}
void build(int lmt)
{
int i, j;
memset(first, -1, sizeof(first)); tot = -1;
for(i = 1;i <= n2; i++)
{
add(st, i, 1);
for(j = 1;j <= m; j++) if(adj[i][j] == 1) add(i, n2 + j, 1);
}
for(i = 1;i <= m; i++)
if(in[i] > lmt) add(i + n2, ed, lmt);
else add(i + n2, ed, in[i]);
}
int sap()
{
int tot_flow;
int now_flow, found, min;
int i, j, t;
memset(dist, 0, sizeof(dist));
memset(now, -1, sizeof(now));
memset(cnt, 0, sizeof(cnt));
i = st;
tot_flow = 0; now_flow = oo;
cnt[0] = n;
while(dist[st] < n)
{
cur[i] = now_flow; found = 0;
if(now[i] == -1) t = first[i];
else t = now[i];
while(t != -1)
{
j = e[t].v;
if(e[t].cap > 0 && dist[j] + 1 == dist[i])
{
found = 1; now[i] = t;
if(e[t].cap < now_flow) now_flow = e[t].cap;
pre[j] = t; i = j;
if(i == ed)
{
tot_flow += now_flow;
while(i != st)
{
e[pre[i]].cap -= now_flow;
e[pre[i]^1].cap += now_flow;
i = e[pre[i]].u;
}
now_flow = oo;
}
break;
}
t = e[t].next;
}
if(found) continue;
if(--cnt[dist[i]] == 0) break;
min = n - 1;
t = first[i];
while(t != -1)
{
if(e[t].cap > 0 && dist[e[t].v] < min)
{
min = dist[e[t].v];
now[i] = t;
}
t = e[t].next;
}
dist[i] = min + 1;
cnt[dist[i]]++;
if(i != st)
{
i = e[pre[i]].u;
now_flow = cur[i];
}
}
return tot_flow;
}
void solve()
{
int high = n2;
int low = 0;
int mid;
int res;
while(low < high)
{
mid = (low + high) >> 1;
build(mid);
res = sap();
if(res >= n2) high = mid;
else low = mid + 1;
}
printf("%d\n", low);
}
int main()
{
while(init()) solve();
return 0;
}
topcoder变绿了
2009年9月11日 17:16
好久没有去topcoder做题了，昨晚做了250分和500分，可怜的500分被challenge掉，呵呵，还有在那个房间里我challenge掉了3个，哈哈，爽！
