求助：父母入关只给了一个月，可以办延期吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Visa - 签证

求助：父母入关只给了一个月，可以办延期吗？

求助：父母入关只给了一个月，可以办延期吗？# Visa - 签证

h*t2016-12-27 08:12

1 楼

Given a graph (any type - Directed acyclic graph or undirected graphs with
loops), find a minimal set of vertices which affect all the edges of the
graph. An edge is affected if the edge is either originating or terminating
from that vertex.

p*c2016-12-27 08:12

2 楼

求助：父母入关B1 visa只给了一个月，可以办延期吗？
在美国待了半年，12月初回去的。因为需要，今天又回到美国。结果海关只给了一个月
。能不能申请延期？有可能批准吗？需要多长时间？谢谢。

g*y2016-12-27 08:12

3 楼

int current_k = N; //global
void VC(int k, int start_v){
if(all_edge_covered(G) && kcurrent_k = k;
return;
}
if(k == current_k - 1) return; //剪枝
for(; start_v<=N; start_v++){
if(!edge_list[start_v].empty()){ //剪枝
list temp_edge_list = edge_list[start_v];
clear_edge(start_v,G);
VC(k+1, start_v+1);
if(curent_k == k+1) return; //剪枝
reset_edge(start_v,temp_edge_list,G);
}//endif
}//endfor
}//endVC

g*y2016-12-27 08:12

4 楼

今天晚上刚刚开始学习backtrack+剪枝(大家不要笑，我刚刚转行的，算法背景不行的)
，呵呵，正好看到这个做做练习，不知道有没有大牛来看看我这个有没有什么问题。

【在 g*******y 的大作中提到】

: int current_k = N; //global
: void VC(int k, int start_v){
: if(all_edge_covered(G) && k: current_k = k;
: return;
: }
: if(k == current_k - 1) return; //剪枝
: for(; start_v<=N; start_v++){
: if(!edge_list[start_v].empty()){ //剪枝
: list temp_edge_list = edge_list[start_v];

s*x2016-12-27 08:12

5 楼

not necessarily connected, so the minimal set of affect differs from the
nodes in a minimal spanning tree.

of
1

h*t2016-12-27 08:12

6 楼

this problem has nothing to do with MST

of
1

g*y2016-12-27 08:12

7 楼

稍微改进了一下：
int current_k = N;
void VC2(int k, int v){
if(kcurrent_k = k;
return;
}
if(k >= current_k - 1) return; //剪枝
if(v == N) return; //没有下一个顶点了
if(!edge_list[v].empty()){ //是否选择当前顶点
list temp_edge_list = edge_list[v];
clear_edge(v,G);
VC2(k+1, v+1);
reset_edge(v,temp_edge_list,G);
}//endif
VC2(k, v+1); //跳过当前顶点，考察下一个
}//endVC2

g*y2016-12-27 08:12

8 楼

how do you reduce clique problem to spanning tree problem????????
It's either you or me who don't well understand the spanning tree/clique
problem.

a*e2016-12-27 08:12

9 楼

Well, after a careful thoughts, I think you are right, sorry for my hasty reply. This problem is much more difficult than I thought.
How about this approach:
(1) Detect all quasi-cliques (using absolute threshold=2, i.e., in the quasi-clique, each node should have a degree>=2). Save the nodes to a set, say A.
(2) Among each quasi-clique, delete a node, which satisfies the following two conditions: <1> the node is not connected to other nodes that do not belong to the quasi-clique, <2> among the

【在 h***t 的大作中提到】

: this problem has nothing to do with MST
:
: of
: 1

D*D2016-12-27 08:12

10 楼

All the nodes need to be in MST, while the original problem doesn't require
that

【在 a*****e 的大作中提到】

: Well, after a careful thoughts, I think you are right, sorry for my hasty reply. This problem is much more difficult than I thought.
: How about this approach:
: (1) Detect all quasi-cliques (using absolute threshold=2, i.e., in the quasi-clique, each node should have a degree>=2). Save the nodes to a set, say A.
: (2) Among each quasi-clique, delete a node, which satisfies the following two conditions: <1> the node is not connected to other nodes that do not belong to the quasi-clique, <2> among the

e*n2016-12-27 08:12

11 楼

It is the famous Vertex Cover problem,
Branch and bound works great for this problem.
For any edge, one of the endpoints would be in the
optimal solution. Try all possible combination of
the endpoints of the edges, it would be a
2^k algorithm where k is the size of the solution.

terminating

【在 h***t 的大作中提到】

: Given a graph (any type - Directed acyclic graph or undirected graphs with
: loops), find a minimal set of vertices which affect all the edges of the
: graph. An edge is affected if the edge is either originating or terminating
: from that vertex.