锘??xml version="1.0" encoding="utf-8" standalone="yes"?>
]]>
]]>
鑳藉惁鍊熶綘瀹屾暣鐨勪唬鐮佸涔犲涔犲憿~
榪欐槸鎴戠殑閭:
weihaoo2@163.com
璋㈣阿鍟妦
]]>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 20;
struct point_T {
int x, y;
};
point_T st, ed[MAXN * MAXN];
char map[MAXN][MAXN];
int board[MAXN][MAXN];
int row, col, cnt;
double mat[MAXN * MAXN][MAXN * MAXN];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
bool ok(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col && (map[x][y] == '@' || map[x][y] == '.' || map[x][y] == '$');
}
void floodfill(int x, int y) {
board[x][y] = ++ cnt;
for(int i = 0; i < 4; i ++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(ok(tx, ty) && board[tx][ty] == -1) {
floodfill(tx, ty);
}
}
}
bool gauss(int n) {
int i, j, row, idx;
double buf, maxx;
for(row = 0; row < n; row ++) {
for(maxx = 0, i = row; i < n; i ++) {
if(maxx < fabs(mat[i][row])) {
maxx = fabs(mat[i][row]);
idx = i;
}
}
if(maxx == 0) return false;
if(idx != row) {
for(i = row; i <= n; i ++)
swap(mat[row][i], mat[idx][i]);
}
for(i = row + 1; i < n; i ++) {
buf = mat[i][row] / mat[row][row];
for(j = row; j <= n; j ++)
mat[i][j] -= buf * mat[row][j];
}
}
for(i = n - 1; i >= 0; i --) {
for(j = i + 1; j < n; j ++)
mat[i][n] -= mat[i][j] * mat[j][j];
mat[i][i] = mat[i][n] / mat[i][i];
}
return true;
}
int main() {
int i, j, k, l, cn;
while(scanf("%d%d", &row, &col) != EOF) {
cn = 0;
for(i = 0; i < row; i ++) {
scanf("%s", map[i]);
for(j = 0; j < col; j ++) {
if(map[i][j] == '@') {
st.x = i;
st.y = j;
}else if(map[i][j] == '$') {
ed[cn].x = i;
ed[cn].y = j;
cn ++;
}
}
}
memset(board, -1, sizeof(board));
cnt = -1;
floodfill(st.x, st.y);
for(i = 0; i < cn; i ++) {
if(board[ed[i].x][ed[i].y] != -1)
break;
}
if(i == cn) {
printf("-1\n");
continue;
}
memset(mat, 0, sizeof(mat));
int now, tx, ty, num;
for(i = 0; i < row; i ++) {
for(j = 0; j < col; j ++) {
if(board[i][j] != -1) {
now = board[i][j];
num = 0;
for(k = 0; k < 4; k ++) {
tx = i + dir[k][0];
ty = j + dir[k][1];
if(ok(tx, ty)) {
num ++;
mat[now][board[tx][ty]] = -1;
}
mat[now][now] = num;
mat[now][cnt + 1] = num;
}
}
}
}
for(i = 0; i < cn; i ++) {
l = board[ed[i].x][ed[i].y];
memset(mat[l], 0, sizeof(mat[l]));
mat[l][l] = 1;
}
if(gauss(cnt + 1))
printf("%.6lf\n", mat[board[st.x][st.y]][board[st.x][st.y]]);
else
printf("-1\n");
}
return(0);
}
]]>
==>涓轟粈涔堝湪寤哄騫跨煩闃墊椂鏄痬at[i][i - 1] = -b, mat[i][i + 1] = -a,mat[i][i] = a + b; 鑰屼笉鏄痬at[i][i - 1] = -a, mat[i][i + 1] = -b, mat[i][i] = a + b;
]]>
]]>
鏈夌殑鍟妦鍒濆鐨勬椂鍊欏S榪涜浜嗚祴鍊紐榪欎釜S杈懼埌涓涓緢寮虹殑鍓灊鐨勫憿
]]>
]]>
]]>
]]>
]]>
]]>
鍏跺疄鍏抽敭鍦ㄤ簬寤哄浘鐨勮繃縐皛~涓婅竟閭d釜妯℃澘鍏跺疄閫熷害宸埆涓嶆槸寰堝ぇ
]]>
]]>
]]>
]]>
榪欓噷娌℃湁浠g爜鏍煎紡
鑷繁澶嶅埗ALT + F8涓涓?br>
#include<stdio.h>
#include<string>
#define Min(a,b) a>b?b:a
struct DP{
int score;
int next;
int time;
}dp[32768];
struct Homework{
int deadlion,time;
char name[101];
}hw[15];
char ans[15][101];
int n;
void dfs(int k)
{
int i,min,cnt,time,d=k,id,score,next,t;
char ch[16];
memset(ch,'0',sizeof(ch));
i = 14;
d = k;
cnt = 0;
ch[15] = 0;
while(d)
{
if(d&1)
{
cnt += d&1;
ch[i] = (d&1) + '0';
id = i;//濡傛灉鍙湁涓涓?錛宨d鍙互璁板綍涓?鐨勪綅瀛?br>}
i --;
d >>= 1;
}//杞寲鎴愪簩榪涘埗
if(cnt == 1)//鏈搴曚笅鐨勬儏鍐?鍙畬鎴愪簡涓縐嶄綔涓?br>{
id = 14 - id;
if(hw[id].deadlion >= hw[id].time)
dp[k].score = 0;
else
dp[k].score = hw[id].time - hw[id].deadlion;
dp[k].time = hw[id].time;
dp[k].next = id;
return ;
}
min = 0x7FFFFFFF;
for(i=0;i<15;i++)
{
if(ch[i]=='1')
{
id = 14 - i;
int kk = k - (1<<id);
if(dp[kk].time == -1)
dfs(kk);
time = dp[kk].time + hw[id].time;
score = dp[kk].score;
if(hw[id].deadlion < time)
score += (time-hw[id].deadlion);
if(score < min || score == min && strcmp(hw[id].name,hw[next].name)<0)
{
if(score<min)
next = id;
min = score;
t = time;
}
}
}
dp[k].score = min;
dp[k].next = next;
dp[k].time = t;
}
int main()
{
int T,i,k;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
k = (1<<n)-1;//涓鍏辨湁榪欎箞澶氬彲鑳?br>for(i=0;i<=k;i++)
dp[i].time = -1;
for(i=0;i<n;i++)
scanf("%s%d%d",hw[i].name,&hw[i].deadlion,&hw[i].time);
dfs(k);
printf("%d\n",dp[k].score);
//杈撳嚭鍚嶅瓧
for(i=0;i<n;i++)
{
strcpy(ans[i],hw[ dp[k].next ].name);
k = k - (1<<(dp[k].next));
}
for(i=n-1;i>=0;i--)
puts(ans[i]);
}
return 0;
}
]]>
鍦ㄧ嚎鐙傜瓑
]]>
]]>